LeetCode刷题【剑指 Offer 38】字符串的排列

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

回溯基本操作了

解题思路

回溯基本操作了

代码

class Solution {


    private List<String> list;

    private Integer length;

    public String[] permutation(String s) {
        list = new ArrayList<>();
        length = s.length();
        boolean[] visited = new boolean[s.length()];
        dfs(s.toCharArray(),visited,0,new char[s.length()]);
        String[] res = new String[list.size()];
        int i = 0;
        for (String s1 : list) {
            res[i] = s1;
            i++;
        }
        return res;
    }


    private void dfs(char[] charArr,boolean[] visited,int index,char[] newCharArr){
        if (index==length){
            list.add(new String(newCharArr));
            return;
        }
        Set<Character> sameChar = new HashSet<>();
        for (int i = 0; i < charArr.length; i++) {
            if (visited[i]){
                continue;
            }
            if (sameChar.contains(charArr[i])){
                continue;
            }
            sameChar.add(charArr[i]);
            visited[i] = true;
            newCharArr[index] = charArr[i];
            dfs(charArr,visited,index+1,newCharArr);
            visited[i] = false;
        }
    }
}