《剑指offer》 第38题 字符串的排序

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

本题的常规解法还是以递归解法为主，学有余力的可以用巧劲解题。可以参考题解的讨论中，五头镜子这位大佬的总结。
递归思路：求整个字符串的排序，将递归设计成两步，步骤如下，第一步求所有出现在第一个位置的字符，也就是将第一个字符和后面所有字符交换，第二步固定第一个字符，求后面所有字符的排序。进入下一次递归调用时，则是将所有的字符和第二个字符交换，然后固定之后，求后面所有字符的排序。
  以abc为例，首先是abc,bac,cba三种，再求abc固定a后的排序方式，此时调用递归，则原问题的子问题变成了求bc的排序方式。同理bac和cba的子问题变成了求ac,ba的排序方式。
  注意输出的排序方式是字典序，因此需要排序。另外，java中的StringBuilder和StringBuffer在操作字符串时，效率比String高，推荐使用。还有一个点要注意的是，需要去重。去重也有好几种处理方法，1.在遍历的过程中应该写进行去重的比较判断的逻辑。2.在java中，使用实现了set接口的工具类即可，如TreeSet，HashSet，使用这些结构在添加的时候就自动去重了。在不同类的选择上，就可以出现多种写法了。
写法1：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        StringBuilder buffer = new StringBuilder(str); //使用StringBuilder       

        ArrayList<String> list1 = PermutationHelp(buffer);

        HashSet<String> set = new HashSet<>(list1);//构造包含list所有元素的HashSet
        ArrayList<String> list2 = new ArrayList<String>(set);//再装到数组中
        Collections.sort(list2);//进行字典序排序
        return list2;
    }

    public ArrayList<String> PermutationHelp(StringBuilder str){
        ArrayList<String> result = new ArrayList<>();//用来装所有结果的数组
        if (str.length()==1){//递归终止条件
            result.add(str.toString());
        }else {
            for (int i=0;i<str.length();i++){
                //下面三句是将字符串进行交换
                char temp = str.charAt(i);
                str.setCharAt(i,str.charAt(0));
                str.setCharAt(0,temp);
                //交换后，除去刚刚交换的字符串，剩余的字符串继续调用递归
                StringBuilder buf = new StringBuilder(str.substring(1));
                ArrayList<String> arrayList = PermutationHelp(buf);
                //到这里说明某一次交换的递归完成，此时需要将结果添加
                for (int j=0;j<arrayList.size();j++){
                //添加字符串[start,end）中的字符串
                    result.add(str.substring(0,1)+arrayList.get(j));
                }
                //temp=str.charAt(0);
                //str.setCharAt(0,str.charAt(i));
                //str.setCharAt(i,temp);
//上面三句是将换出的字符再换回去，但实际可以省略
//不换回去，从整体上来看，顺序乱了，但是遍历时依旧会遍历所有情况，在纸上画一画很清楚。
//这3句可以省略，因为最终使用了Collections的排序方法，使得即使不换回去，排序过后依旧字典序
//添加这三句代码，就有点回溯的味道了。
            }
        }
        return result;
    }
}
//result.add(str.substring(0,1)+arrayList.get(j));不容易理解，如abc定住a后，子问题是bc
//递归的返回值，定b后，返回c，则str取b，arrayList取c，合并成bc添加到result，
//递归的返回值，定c后，返回b，则str取c，arrayList取b，合并成cb添加到result，
//arrayList是拿到的就是result
//再向上返回时，str变成a，则arrayList是bc和cb的集合，所以需要一个for循环。拼接成abc和acb

写法2：由于TreeSet底层红黑树实现了排序，所以用TreeSet就不用调用排序方法。对比方法1，只需要修改Permutation方法中的几行，剩下的PermutationHelp方法完全一样

import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        StringBuilder buffer = new StringBuilder(str); //使用StringBuilder             
        ArrayList<String> list1 = PermutationHelp(buffer);     
        TreeSet<String> set = new TreeSet<>(list1);//构造一个包含list所有元素的TreeSet
        ArrayList<String> list2 = new ArrayList<String>(set);//再装到数组中       
        return list2;
    }

    public ArrayList<String> PermutationHelp(StringBuilder str){
        ArrayList<String> result = new ArrayList<>();
        if (str.length()==1){
            result.add(str.toString());
        }else {
            for (int i=0;i<str.length();i++){
                char temp = str.charAt(i);
                str.setCharAt(i,str.charAt(0));
                str.setCharAt(0,temp);
                StringBuilder buf = new StringBuilder(str.substring(1));
                ArrayList<String> arrayList = PermutationHelp(buf);
                for (int j=0;j<arrayList.size();j++){
                    result.add(str.substring(0,1)+arrayList.get(j));
                }
            }
        }
        return result;
    }
}

写法3：在遍历的过程中，进行重复的判断。

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
     public ArrayList<String> Permutation(String str) {
        StringBuilder strBuilder = new StringBuilder(str);
        ArrayList<String> result = PermutationHelp(strBuilder);
        Collections.sort(result);
        return result;
    }

    public ArrayList<String> PermutationHelp(StringBuilder str){
         ArrayList<String> result = new  ArrayList<String>();
        if(str.length() == 1)
            result.add(str.toString());
        else{
            for(int i = 0; i < str.length(); i++){
                if(i== 0  || str.charAt(i) != str.charAt(0)){//这里判断
                    char temp = str.charAt(i);
                    str.setCharAt(i, str.charAt(0));
                    str.setCharAt(0, temp);
                    StringBuilder buf = new StringBuilder(str.substring(1));
                    ArrayList<String> arrayList = PermutationHelp(buf);
                    for(int j =0; j < arrayList.size(); j++)
                        result.add(str.substring(0,1)+arrayList.get(j));  
                    temp = str.charAt(0);
                    str.setCharAt(0, str.charAt(i));
                    str.setCharAt(i, temp);
                }               
            }
        }
        return result;
    }
}
//很神奇的是，如果不交换回去，就不用调用集合类的排序方法。下面的写法也可以跑起来
//这个倒是没弄清楚。不知道是测试用例不全还是什么原因。
import java.util.ArrayList;
public class Solution {
     public ArrayList<String> Permutation(String str) {
        StringBuilder strBuilder = new StringBuilder(str);
        ArrayList<String> result = PermutationHelp(strBuilder);
        return result;
    }

    public ArrayList<String> PermutationHelp(StringBuilder str){
         ArrayList<String> result = new  ArrayList<String>();
        if(str.length() == 1)
            result.add(str.toString());
        else{
            for(int i = 0; i < str.length(); i++){
                if(i== 0  || str.charAt(i) != str.charAt(0)){
                    char temp = str.charAt(i);
                    str.setCharAt(i, str.charAt(0));
                    str.setCharAt(0, temp);
                    StringBuilder buf = new StringBuilder(str.substring(1));
                    ArrayList<String> arrayList = PermutationHelp(buf);
                    for(int j =0; j < arrayList.size(); j++)
                        result.add(str.substring(0,1)+arrayList.get(j));                  
                }                
            }
        }
        return result;
    }
}