刷题记录第22题，上一题：数据流中的中位数，本题地址：字符串的排列。
题目描述：
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
这道题是一道典型的回溯法问题。在之前的八皇后问题的博客中也采用了回溯的思想。
在算法小抄的一书中说到：解决一个回溯问题，实际上就是一个决策树的遍历过程，且这个算法做的过程很基础，就是穷举过程。
回溯算法的代码框架如下：
private void backtrack(路径， 选择列表){
if 满足结束条件{
result.add(路径)
return
}
for 选择 in 选择列表{
做选择
backtrack(路径， 选择列表)
撤销选择
}
}
其核心也就在于，再for循环的递归，在递归调用前做出选择，在递归调用结束后撤销选择。
本题中输入的字符串，没有明确说明是否是每个字母只出现一次，所以这里的字母其实可以出现多次。也就是比如aaa这样的字符串。
解决该问题的一种较为直观的思路是，我们首先生成所有的排列，然后进行去重。而另一种思路是我们通过修改递归函数，使得该递归函数只会生成不重复的序列。
class Solution {
private List<String> list;
boolean[] vis;
public String[] permutation(String s) {
list = new ArrayList<>();
vis = new boolean[s.length()];
backtrack(s.toCharArray(), 0, s.length(), new StringBuffer());
// 去重
HashSet<String> strings = new HashSet<>(list); // List<String> list;
String[] res = new String[strings.size()];
int idx = 0;
for (String string : strings) {
res[idx++] = string;
}
return res;
}
// i 表示当前位置，n表示字符串长度
private void backtrack(char[] arr, int i, int length, StringBuffer stringBuffer) {
if(i == length && stringBuffer.length() > 0){
list.add(stringBuffer.toString());
return;
}
for (int j = 0; j < length; j++) {
if(vis[j])
continue;
vis[j] = true;
stringBuffer.append(arr[j]);
backtrack(arr, i + 1, length, stringBuffer);// 探测下一个位置
stringBuffer.deleteCharAt(stringBuffer.length() - 1);
vis[j] = false;
}
}
}
另一种，在递归函数中去重的思路为：在递归函数中设定一个规则，保证在填每一个空位的时候重复字符只会被填入一次。具体地，我们首先对原字符串排序，保证相同的字符都相邻，在递归函数中，我们限制每次填入的字符一定是这个字符所在重复字符集合中「从左往右第一个未被填入的字符」，即如下的判断条件：
if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
continue;
}
