题目来自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))returnvisited = 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

 提交结果如下: