题解 | #JZ27 字符串的排列#

java 字典全排列

import java.util.*;

/**
 * @Author zhongyk
 */
public class SolutionJZ27 {
    public ArrayList<String> Permutation(String str) {
        Set<String> res=new LinkedHashSet<>(10);
        if (str.length() == 0) {
            return null;
        }
        //下面4行让第一个字符串为整体值最小的字符串。比如abcd是值最小的4个由a,b,c,d组成的字符串
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        str=new String(arr);
        res.add(str);

        //以下循环是为了找到值不断递增的字符串，并加入到结果集res中去。比如，比abcd大的里面，最小的字符串为abdc
        //直到取到最大值之后就退出
        while (true){
            str=dicSortNext(str);
            if("finished".equals(str)){
                break;
            }else {
                res.add(str);
            }
        }
        ArrayList<String> result=new ArrayList<>(res);
        return result;
    }
    //该方法的目的是找到下一个比当前字符串的值大的中，最小的字符串。
    private String dicSortNext(String str) {
        char[] arr=str.toCharArray();
        int len=str.length();
        //从后往前找，找到不递增的那个数，定位第一个字符。比如12543，从后往前不递增的那个字符就是2
        int i=len-2;
        while (i>=0&&arr[i]>=arr[i+1]) {
            i--;
        }
        //找不到就意味着找完了(当前为最大字符)，直接返回
        if(i==-1) return "finished";
        //从后往前找，找到一个比上面定位的第一个字符大的字符。比如12543，从后往前找一个比2大的数，就是3了
        int j=len-1;
        while (j>=0&&arr[j]<=arr[i]){
            j--;
        }
        //交换两个数的位置。比如12543，交换位置后为13542
        char tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
        //把arr[i]字符之后的倒序。比如13542，倒序之后为13245
        for(int a=i+1,b=len-1;a<b;a++,b--){
            tmp =arr[a];
            arr[a]=arr[b];
            arr[b]=tmp;
        }

        return new String(arr);
    }
}