字符串的排列

链接：https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?answerType=1&f=discussion
来源：牛客网

开始想的是列出所有可能，找规律，发现从后往前找，麻烦地令人绝望，试着从前往后找，结果可行！
第一步，先是例行的排除掉输入str为空或长度为0的情况。
第二步，输入str长度为1，那就一种可能，直接返回
第三步，开始正式挑战这个题目。思路就是用递归。
先把str转换成个char数组，然后排个序。这样里面的字符就都是按字典顺序排列，而且重复的在一起！后面的操作就方便了。
假设最后组好的字符串叫result，那对result的每一位都依字典顺序列出各种可能，重复的跳过。
例如：“abc”，那result的第一位依次是a,b,c。这时没确定位置的只剩下两个字符啦，它们的排列顺序很简单，就别麻烦递归了，直接用前面组好的字符串加上a+bc和a+cb。（同理b+ac和b+ca等等）（只剩下两个字符就是递归的结束条件）
那复杂点的呢？也没问题，例如"aabccde"。那result的第一位是a,b,c,d,e。对a来说，下一位是b,c,d,e。对ab来说，下一位是c,d,e。依次类推，用递归完成所有排序。
代码如下：
import java.util.*;
public class Solution {
public ArrayList<string> Permutation(String str) {
ArrayList<string> al=new ArrayList<string>();
if(str==null||str.length()==0){
return al;
}
int len=str.length();
if(len==1){
al.add(str);
return al;
}
char[] chars=str.toCharArray();
Arrays.sort(chars);
zuhe(chars,"",al);
return al;
}</string></string></string>

public void zuhe(char[] meat,String target,ArrayList<String> al){
    int len=meat.length;
    if(len==2){
        if(meat[0]==meat[1]){
            al.add(target+meat[0]+meat[1]);
        }else{
            al.add(target+meat[0]+meat[1]);
            al.add(target+meat[1]+meat[0]);
        }
        return;
    }
    char pre=(char)0;
    for(int i=0;i<len;i++){
        if(meat[i]!=pre){
            pre=meat[i];                
            String buf=target+meat[i];
            char[] m2=meat.clone();
            m2[i]=(char)0;
            Arrays.sort(m2);
            zuhe(Arrays.copyOfRange(m2,1,len),buf,al);                
        }
    }
}

}