39、字符串的排列

题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

链接：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7

思路：我们可以把一个字符串看成两个部分：第一个字符 + 后面的所有字符
首先，我们求所有可能出现在第一个位置的字符，即将第一个字符和后面所有的字符交换。确定了第一个字符后，求后面所有字符的排列。

后面所有字符的排列和上面的过程一样，把后面所有的字符看成两个部分：第一个字符 + 后面的所有字符

可以看出，典型的递归思路。

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    
    ArrayList<String> result = new ArrayList<String>();
    
    public ArrayList<String> Permutation(String str) {
        if(str==null || str.length()==0) return result;
        permutation(str.toCharArray(), 0);
        Collections.sort(result);
        return result;
    }
    
    // start表示拿第start个字符和后面的字符进行交换
    private void permutation(char[] str, int start){
        // 当start超过数组长度时，遍历数组，将字符串放入List中；否则继续交换start字符，确定后面字符的排列
        if(start<str.length){
            for(int i=start; i<str.length; ++i){
                // 当后面的字符和当前字符一样，不用交换
                // i == start是为了继续递归，将结果放入List中
                if(i == start || str[i] != str[start]){
                    char temp = str[i];
                    str[i]=str[start];
                    str[start]=temp;
                    
                    permutation(str, start+1);
                    
                    temp = str[i];
                    str[i]=str[start];
                    str[start]=temp;
                }
            }
        }else{
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<str.length;++i){
                sb.append(str[i]);
            }
            result.add(sb.toString());
        }
    }
    
    
    
}