剑指Offer_#38_字符串的排列
Contents
题目
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]限制：
1 <= s 的长度 <= 8思路分析
全排列
根据高中数学学过的排列组合相关知识，n个元素的所有排列数是
。
推导思路很简单，就是一位一位地去固定元素，第1个位置有
种可能，第2个位置有
种可能，...最后1位有一种可能。把这些乘起来就得到
。
这个思路可以直接应用到这题上面，下图很好的展示了这个思路。
得到所有排列的过程
- 先固定第1位，有3个选择：与自己交换（即保持不变），与第2位交换，与第3位交换
- 然后固定第2位，有2个选择：与自己交换，与第3位交换
- 固定最后一位，只有1个选择：与自己交换。因为前面2个位置已经固定，最后1位只能是剩下的那个
总结规律
这是一个递归的过程
- 递推过程
- 每一次需要将当前位置字符和后面的所有字符交换
- 每一次待固定的位置向后移一位
- 终止条件
- 当固定到最后一位的时候，得到一个排列
重复字符的处理
设想输入的字符串当中包含了重复字符的情况，那么最后得到的结果也会有重复。如何解决这一问题呢？
设当前位置的字符为
，在当前位置与后边所有位的字符交换位置，假如在这个范围内（从当前位置到末尾的范围），有两个相同的字符
和
,那么
与
和
进行交换的结果是一样的。
所以当第二次遇到某个字符时，就不必要再进行交换了，这个过程就是剪枝，下图很好的展示了这个过程。
代码实现：
维护一个HashSet变量，每次将遇到的字符存入，第二次遇到相同字符时，跳过本轮循环。
解答
class Solution {
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
recur(0);
//参数是为了指定返回数组的类型String[res.size()]
return res.toArray(new String[res.size()]);
}
//在x位置处尝试所有可能的字符（和后边的所有字符交换位置）
void recur(int x){
//终止条件
if(x == c.length - 1){
res.add(String.valueOf(c));
//递归终止
return;
}
HashSet<Character> set = new HashSet<>();
//递推过程：将x后面的所有字符交换到x处
for(int i = x;i <= c.length - 1;i++){
//在循环中，如果遇到重复字符，剪枝
if(set.contains(c[i])) continue;
//不是重复字符，则继续
set.add(c[i]);
swap(i,x);
//开启递归子函数，去尝试下一位的所有可能
recur(x+1);
//恢复交换
swap(i,x);
}
}
//交换索引indexA和索引indexB位置的字符
void swap(int indexA,int indexB){
char tmp = c[indexA];
c[indexA] = c[indexB];
c[indexB] = tmp;
}
}