题目
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
要求
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
分析
假如我们固定第一个字母，然后依次将第一个字母依次与子串中的其他字母进行交换。也就是固定第一个字母，只需要求出后面子串的排列个数就可以得到结果，因此考虑使用递归算法。递归的出口就是只剩下一个字符的时候。
但是，有一个问题是，加入字符串中有重复的字符，此时会得到重复的结果。
- 思考一
如果一个数与后面的数字相同那么就不进行交换。例如abb,a与第一个b交换得到bab,a与第二个b交换的到bba，这是时候，交换b的结果是abb，所以第二个字符与第三个字符不用交换。但是，字符串是bab，第二个字符和第三个字符不一样，需要交换，因此这个思考行不通。
- 思考二
abb，第一个字符a与第二个字符b交换得到bab，然后考虑第一个字符与第三个字符交换，假如第三个数等于第二个数，第一个数就不再用与第三个数交换了。假如，第二个字符与第三个字符不相同，则进行交换。全排列完成！
abc的递归过程如下图所示：
代码
综上分析，代码如下：
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList <String> result = new ArrayList<String>();
// 字符串为空或者长度为0
if(str == null || str.length() == 0)
{
return result;
}
// 将字符串转化为字符数组
char[]chars = str.toCharArray();
getResult(chars,0,str.length() - 1,result);
Collections.sort(result);
return result;
}
public void getResult(char[] chars,int start,int end,ArrayList <String> result){
if(start == end){
result.add(new String(chars));
}else{
for(int i = start; i < chars.length; i++){
if(i == start || chars[start] != chars[i]){
swap(start,i,chars);
getResult(chars,start + 1,end,result);
swap(start,i,chars);
}
}
}
}
public void swap(int i ,int j, char[] chars){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
需要注意的是： Collections.sort(result);
有的平台少了这句，是不能通过的，这句代码的意思是对得到的list进行排序，默认是按照首字母升序排列的。
