剑指Offer（二十七）字符串排列（Java版 )

爱被打了一巴掌 2021-09-26 23:16 262阅读 0赞

# 一、题目描述 #

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

# 二、代码描述 #

import java.util.*;
    //字典序算法
    //步骤如下：
    //1.从这个序列中从右至左找第一个左邻小于右邻的字符,记录下标为index1 ，如果找不到，说明求解完成。
    //2.从这个序列中从右至左找第一个大于str[index1]的字符，记录下标为index2
    //3.交换index1和index2的字符，对index1+1后的所有字符进行升序排序，此时得到的即为str按字典序的下一个排列
    //4. 重复1~3的步骤，直到全部找完 
    
    public class Solution {
        public ArrayList<String> Permutation(String str) {
               ArrayList<String> res = new ArrayList<>();
    
                if (str != null && str.length() > 0) {
                    char[] seq = str.toCharArray();
                    Arrays.sort(seq); //排列
                    res.add(String.valueOf(seq)); //先输出一个解
    
                    int len = seq.length;
                    while (true) {
                        int p = len - 1, q;
                        //从后向前找一个seq[p - 1] < seq[p]
                        while (p >= 1 && seq[p - 1] >= seq[p]) --p;
                        if (p == 0) break; //已经是“最小”的排列，退出
                        //从p向后找最后一个比seq[p]大的数
                        q = p; --p;
                        while (q < len && seq[q] > seq[p]) q++;
                        --q;
                        //交换这两个位置上的值
                        swap(seq, q, p);
                        //将p之后的序列倒序排列
                        reverse(seq, p + 1);
                        res.add(String.valueOf(seq));
                    }
                }
    
                return res;
            }
    
            public static void reverse(char[] seq, int start) {
                int len;
                if(seq == null || (len = seq.length) <= start)
                    return;
                for (int i = 0; i < ((len - start) >> 1); i++) {
                    int p = start + i, q = len - 1 - i;
                    if (p != q)
                        swap(seq, p, q);
                }
            }
    
            public static void swap(char[] cs, int i, int j) {
                char temp = cs[i];
                cs[i] = cs[j];
                cs[j] = temp;
            }
    }

运行结果：  
![这里写图片描述][70]

[70]: /images/20210923/aa942fc170654143a2daa5369cc3ca7d.png