27.字符串的排列

佚名 7年前 (2019-04-26) 随笔 1507人围观抢沙发百度已收录

题目描述：

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

思路分析：

字典序全排列
1.从后向前找到第一对正序的si-1和si,保存si-1的下标。
2.找到si-1后面最后一个比它大的值，将值和si-1交换。
3.将si-1后面的所有数逆序，即得到当前序列的下一个排列。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码：

/**
字典序全排列
1.从后向前找到第一对正序的si-1和si,保存si-1的下标。
2.找到si-1后面最后一个比它大的值，将值和si-1交换。
3.将si-1后面的所有数逆序，即得到当前序列的下一个排列。
*/
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String>res=new ArrayList<>();
        if(str==null||str.length()==0)
            return res;
        char[]s=str.toCharArray();
        Arrays.sort(s);
        while(true){
            int flag=-1;
            res.add(new String(s));
            for(int i=s.length-1;i>0;i--){  //第一步
                if(s[i-1]<s[i]){
                    flag=i-1;
                    break;
                }
            }
            if(flag==-1)  //如果flag为1，证明该排列已经到了最后一种排列，所以可以退出循环。
                break;
            for(int j=s.length-1;j>flag;j--){  //第二步
                if(s[j]>s[flag]){           
                    char temp=s[j];
                    s[j]=s[flag];
                    s[flag]=temp;
                    break;
                }
            }
            reverse(s,flag+1,s.length-1); //第三步
        }
        return res;
    }
    public void reverse(char[]s,int start,int end){
        while(start<end){
            char temp=s[end];
            s[end]=s[start];
            s[start]=temp;
            start++;
            end--;
        }
    }
}