【Java面试题】字符串排序

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

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

【示例】：
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

【关键点】： 字符串,回溯
回溯的基本思想

【Java】：

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

public class Solution {
    public ArrayList<String> Permutation(String str) {
        StringBuilder sb = new StringBuilder(str);//string不可变，StringBuilder可变
        ArrayList<String> result = new  ArrayList<String>();
        if(sb.length() == 1)result.add(sb.toString());
        else{
            for(int i = 0; i < sb.length(); i++){
                if(i== 0 || sb.charAt(i) != sb.charAt(0)){//字符不重复
                    char temp = sb.charAt(i);//获取第i个字符的内容
                    sb.setCharAt(i, sb.charAt(0));//前两个数交换:a和b交换，
                    sb.setCharAt(0, temp);
                    ArrayList<String> newResult = Permutation(new String(sb.substring(1)));//切去a，递归当前字符为bc
                    for(int j =0; j < newResult.size(); j++){
                        result.add(sb.substring(0,1)+newResult.get(j));//bc+a
                    }
                    //用完还是要放回去的
                    temp = sb.charAt(0);
                    sb.setCharAt(0, sb.charAt(i));
                    sb.setCharAt(i, temp);
                }
            }
            //升序排列
            Collections.sort(result);
        }
        return result;
    }
}