LeetCode-面试题38-字符串的排列

题目

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例：

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

限制：

​ 1 <= s 的长度 <= 8

解题思路

方法1：DFS全排列+剪枝

基本原理通过字符交换的方式，先固定第1位，再固定第2位，一直到固定第n位。

比如固定a，找剩下bc的可能排列，再固定b，找剩下c的可能排列。

之后固定b，找ac的可能排列....直到所有的组合都被找到

特例处理：当初始的字符串有重复的字符时，如aab，需要保证字符只在此为固定一次，即遇到重复的字符时不进行交换直接跳过，即剪枝

方法2：DFS+回溯

全排列问题详解见该文

路径从空开始构建，当DFS深度达到了字符串长度时则添加进去，之后开始回溯，将访问过的状态复原，path弹出

Java代码

class Solution {
    List<String> res = new LinkedList<>();
    public String[] permutation(String s) {
        if(s==null||s.length()==0) return new String[0];
        char[] c = s.toCharArray(); 
        StringHelper(c,0);
        return res.toArray(new String[res.size()]);
    }

    public void StringHelper(char[] c,int start){
        if(start==c.length-1){
            res.add(String.valueOf(c)); // 添加排列
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i=start;i<c.length;i++){
            if(set.contains(c[i])) continue; // 剪枝重复的
            set.add(c[i]);
            // 交换，将c[i]固定在start位置，比如abc，此时固定a
            char temp = c[i];
            c[i] = c[start];
            c[start] = temp;
            // 递归start+1位置，比如abc，此时进入bc的固定再交换，递归
            StringHelper(c,start+1);
            // 恢复交换
            temp = c[i];
            c[i] = c[start];
            c[start] = temp;
        }
    }
}

Python代码

class Solution:
    def permutation(self, s: str) -> List[str]:
        def dfs(s, size, depth, visited, path, res):
            if depth == size: # 路径达到长度了，进行添加
                res.append("".join(path[:]))
                return

            for i in range(size):
                if not visited[i]:
                    # 如果当前节点和前一个节点相同，且他的前一个节点已经被遍历，则跳过
                    if i>0 and s[i]==s[i-1] and not visited[i-1]:continue
                    visited[i] = True # 访问过了
                    path.append(s[i]) # 添加进路径
                    dfs(s, size, depth + 1, visited, path, res) # 开启DFS
                    visited[i] = False # 回溯，状态还原
                    path.pop() # 路径还原
                
        s = list(sorted(s)) # 考虑重复问题，先进行排序
        size = len(s)
        if size == 0:
            return []
        res = []
        path = []
        visited = [False for _ in range(size)]
        dfs(s, size, 0, visited, path, res)
        return res

Java代码2

class Solution {
    public String[] permutation(String s) {
        int len = s.length();
        Set<String> result = new HashSet<>();
        boolean[] visited = new boolean[len];
        char[] charStr = s.toCharArray();
        dfs("",charStr,result,len,visited);
        return result.toArray(new String[0]);
    }

    public void dfs(String s,char[] charStr,Set<String> result,int len,boolean[] visited){
        if(s.length()==len){
            result.add(s);
            return;
        }
        for(int i =0;i<len;i++){
            if(visited[i]){
                continue;
            }
            if(i>0&&charStr[i]==charStr[i-1]&&!visited[i-1]){
                continue;
            }
            visited[i] = true;
            dfs(s+String.valueOf(charStr[i]),charStr,result,len,visited);
            visited[i] = false;
        }
    }
}