剑指offer-27、字符串的排列

题⽬描述

输⼊⼀个字符串，按字典序打印出该字符串中字符的所有排列。例如输⼊字符串 abc ，则按字典序打印出由字符 a , b , c 所能排列出来的所有字符串 abc , acb , bac , bca , cab 和 cba 。
输⼊描述：输⼊⼀个字符串，⻓度不超过9(可能有字符重复)，字符只包括⼤⼩写字⺟
思路及解答

递归回溯（使用Set去重）

看到题目，应该就知道要使⽤回溯了。
通过 ​回溯算法​ 生成所有排列，配合 ​剪枝条件​ 实现去重和字典序输出。关键步骤包括：

• ​固定位置法​：逐个固定每个位置的字符
  
• ​交换策略​：通过交换字符位置生成不同排列
  
• ​去重处理​：使用集合(Set)或排序后跳过重复字符来避免重复排列
  
• ​字典序排序​：最后对结果进行排序
  

1. import java.util.ArrayList;
2. import java.util.Collections;
4. public class StringPermutation {
5.     public ArrayList<String> permutation(String str) {
6.         ArrayList<String> result = new ArrayList<>();
7.         if (str == null || str.length() == 0) {
8.             return result;
9.         }
10.         
11.         char[] chars = str.toCharArray();
12.         permute(chars, 0, result);
13.         Collections.sort(result); // 按字典序排序
14.         return result;
15.     }
16.    
17.     private void permute(char[] chars, int begin, ArrayList<String> result) {
18.         if (begin == chars.length - 1) {
19.             result.add(new String(chars));
20.             return;
21.         }
22.         
23.         for (int i = begin; i < chars.length; i++) {
24.             // 跳过重复字符，避免重复排列
25.             if (i != begin && chars[i] == chars[begin]) {
26.                 continue;
27.             }
28.             
29.             swap(chars, begin, i);
30.             permute(chars, begin + 1, result);
31.             swap(chars, i, begin); // 回溯，恢复原始状态
32.         }
33.     }
34.    
35.     private void swap(char[] chars, int i, int j) {
36.         char temp = chars[i];
37.         chars[i] = chars[j];
38.         chars[j] = temp;
39.     }
40. }

复制代码

• 时间复杂度​：O(n*n!)，n为字符串长度，n!是排列总数，每次排列需要O(n)时间
  
• ​空间复杂度​：O(n!)，需要存储所有排列结果
  

回溯+剪枝法（优化去重）

上面方法主要是通过Set进行去重，也可以将字符数组排序来跳过重复字符：

• ​先排序​：将字符数组排序，使相同字符相邻
  
• ​剪枝策略​：在递归过程中跳过相同字符的重复分支
  
• ​标记数组​：使用boolean数组记录已使用字符
  

1. public class StringPermutation {
2.     public ArrayList<String> permutation(String str) {
3.         ArrayList<String> result = new ArrayList<>();
4.         if (str == null || str.length() == 0) {
5.             return result;
6.         }
7.         
8.         char[] chars = str.toCharArray();
9.         Arrays.sort(chars); // 先排序便于去重
10.         boolean[] used = new boolean[chars.length];
11.         backtrack(chars, used, new StringBuilder(), result);
12.         return result;
13.     }
14.    
15.     private void backtrack(char[] chars, boolean[] used,
16.                          StringBuilder path, ArrayList<String> result) {
17.         if (path.length() == chars.length) {
18.             result.add(path.toString());
19.             return;
20.         }
21.         
22.         for (int i = 0; i < chars.length; i++) {
23.             // 剪枝条件：跳过已使用字符或相同字符的重复分支
24.             if (used[i] || (i > 0 && chars[i] == chars[i-1] && !used[i-1])) {
25.                 continue;
26.             }
27.             
28.             used[i] = true;
29.             path.append(chars[i]);
30.             backtrack(chars, used, path, result);
31.             path.deleteCharAt(path.length() - 1); // 回溯
32.             used[i] = false;
33.         }
34.     }
35. }

复制代码

• 时间复杂度​：O(n*n!)，但剪枝减少了不必要的递归调用
  
• ​空间复杂度​：O(n!)，结果存储空间
  

非递归

此方法算法理解难度较大，非标准解法
用字典序生成下一个排列的算法：

• ​初始排序​：将字符数组按字典序排序
  
• ​找下一个排列​：
  
  
  
  • 从后向前找到第一个升序对
    
  • 交换适当元素
    
  • 反转后缀
    
  
  
• ​循环生成​：直到无法生成下一个排列
  

[code]import java.util.ArrayList;import java.util.Arrays;public class StringPermutation {    public ArrayList permutation(String str) {        ArrayList result = new ArrayList();        if (str == null || str.length() == 0) {            return result;        }                char[] chars = str.toCharArray();        Arrays.sort(chars); // 初始排序        result.add(new String(chars));                while (true) {            int i = chars.length - 2;            // 从后向前找第一个升序对            while (i >= 0 && chars >= chars[i + 1]) {                i--;            }            if (i < 0) break; // 已是最大排列                        int j = chars.length - 1;            // 找到第一个大于chars的字符            while (chars[j]