题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由

字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述

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

输出描述

1. 字符串全排列

2. 不能重复

3. 按照字母顺序升序输出（比如"abc"和"bac","abc"在前，同理如果是"cab"和"cba"需要"cab"在前）

解题思路

1. 这道题整体来说就是递归调用组成和数据然后写入result中，相信刷了leetcode关于那几道
递归调用求数组全排列，这个理解起来应该没啥问题。

2. 首先将输入的字符串转换为字符数组，方便我们查找全排列，当然也可以采用字符串组合的

方式进行递归调用，看个人吧。

3. 将字符串数组当做入参传入getAllPermutation数组进行调用，并且输入数组的起始和终止

下标作为递归调用的边界条件，先讲解getAllPermutation函数.

4. 将入参传入后，我们判断递归的终止条件肯定是start下标大于等于end下标，然后这个时候

的数组数据将其转换为字符串存储到result中。

5. 如果不满足终止条件，那么我们就需要递归调用，我们假设输入的是字符串“abc”,那么数组

表示就是['a', 'b', 'c']，首先我们从0下标开始start下标（即是指向a）,这个时候开始for

循环选定一个字母作为首字母，选定的方法我们就用for循环将后面的字母与start字母进行交

换，此时确定了第一个位置的字母，我们紧接着确定第二个位置的字母，方法同理。只需要修

改start为1即是前一个start+1即可，然后从后面的字母中选取一个交换直到最后递归终止start=end

6. 当我们完成了一次终止条件的时候，此时递归返回我们需要将刚才交换位置的两个数据进

行再次交换，保证回到原始的数组位置（保证数组都是在同一个顺序下开始进行搜索的避免大

量重复）

7. 依次搜索即可完成得到所有的结果。

8. 在得到结果后，因为题目本身需求需要保证其有序性，按照这种每次选字母的方式组合最

后通过率只有50%，因为不能保证有序，我在递归过程中也没有采取对应的排序检测措施，所

以最后我需要对获得的result这个ArrayList进行字符串排序操作

9. 字符串排序操作我采用的低位优先排序，字符串排序主要分两种低位优先排序和高位优先

排序，其中低位优先排序指的是从右至左进行排序，而高位则是从左至右排序，高位优先排序

效率更高（但是代码更麻烦），我选的低位优先的方法。

10. 低位优先的思想：每次从里面取出一位来进行排序，排序的方法是将相同的字符作为一组

，计算其频率。然后再将频率转换为索引，根据其索引可以将字符串写入到一个辅助的字符串

数组中，最后再将这个辅助数组的字符串回写到原始字符串数组保证其有序性。（具体内容参

见算法第四版的字符串排序）

JAVA源代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.length()==0) return result;
        char[] ch = str.toCharArray();
        getAllPermutation(result, ch, 0, ch.length-1);
        lsd_sort(result, result.get(0).length());
        return result;
    }
    
    private static void getAllPermutation(ArrayList<String> result, char[] ch, int start, int end) {
        if (start >= end) {
            String temp = String.valueOf(ch);
            if (!result.contains(temp)) result.add(temp);
            return;
        } else {
            for (int i=start; i<=end; i++) {
                exch(ch, i, start);
                getAllPermutation(result, ch, start+1, end);
                exch(ch, i, start);
            }
        }
    }
    
    private static void exch(char[] ch, int i, int j) {
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }
    
    //字符串低位优先排序
    private static void lsd_sort(ArrayList<String> result, int W) {
        int N = result.size();
        int R = 256;
        String[] aux = new String[N];
        for (int d = W-1; d>=0; d--) { 
            int[] count = new int[R+1];
            //计算频率
            for (int i=0; i<N; i++) {
                count[result.get(i).charAt(d)+1]++;
            }
            //将频率转换为索引
            for (int r=0; r<R; r++) {
                count[r+1] += count[r];
            }
            //将元素分类
            for (int i=0; i<N; i++) {
                aux[count[result.get(i).charAt(d)]++] = result.get(i);
            }
            result.clear();
            //回写
            for (int i=0; i<N; i++) {
                result.add(aux[i]);
            }
        }
    }
}