leetcode--字符串的排列

题目来自LeetCode，链接：面试题38. 字符串的排列。具体描述为：输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例：

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

这种全排列的题目其实就是典型的DFS+回溯，老套路了。这里用的是交换法，也就是对于第i个字符，我们都尝试将其跟后面的字符交换一下得到一个新的排列（因为不能有重复元素，所以后面的字符如果跟第i个字符一样的话就不用交换了），然后我们需要遍历所有的i（从0到s.lenght()-1），这就是DFS在做的事情，至于回溯，则是在交换字符之后会进入下一层的DFS，结束这个DFS之后需要再交换一次字符以恢复交换之前的状态。全排列的时间复杂度莫得办法就是$O(n!)$，空间复杂度为$O(n)$（递归栈需要的空间，中间判重直接用的定长数组就直接看成$O(1)$了）。

JAVA版代码如下：

class Solution {
    private char[] chars;
    private List<String> result;

    private void swap(int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
    private void dfs(int idx) {
        if (idx == chars.length - 1) {
            result.add(new String(chars));
            return;
        }
        boolean[] visited = new boolean[26];
        visited[chars[idx] - 'a'] = true;
        dfs(idx + 1);
        for (int i = idx + 1; i < chars.length; ++i) {
            if (!visited[chars[i] - 'a']) {
                visited[chars[i] - 'a'] = true;
                swap(idx, i);
                dfs(idx + 1);
                // 回溯
                swap(idx, i);
            }
        }
    }
    public String[] permutation(String s) {
        chars = s.toCharArray();
        result = new LinkedList<>();
        dfs(0);
        return result.toArray(new String[0]);
    }
}

提交结果如下:

Python版代码如下：

class Solution:
    def permutation(self, s: str) -> List[str]:
        chars = [ss for ss in s]
        n = len(chars)
        result = []

        def dfs(idx):
            if idx == n - 1:
                result.append(''.join(chars))
                return
            visited = set()
            visited.add(chars[idx])
            dfs(idx + 1)
            for i in range(idx + 1, n):
                if not chars[i] in visited:
                    visited.add(chars[i])
                    chars[idx], chars[i] = chars[i], chars[idx]
                    dfs(idx + 1)
                    chars[idx], chars[i] = chars[i], chars[idx]
        dfs(0)
        return result

提交结果如下: