27、字符串的排列

题⽬描述

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

输⼊描述：输⼊⼀个字符串，⻓度不超过9(可能有字符重复)，字符只包括⼤⼩写字⺟

思路及解答

在看回溯系列算法题时，可以先学习整体框架：回溯算法

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

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

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

class Solution {
    // 主函数
    public List<String> permutation(String str) {
        if (str == null || str.length() == 0) {
            return new ArrayList<>();
        }
        
        char[] chars = str.toCharArray();
        Arrays.sort(chars); // 先排序便于去重
        
        // 保存最终结果
        List<String> res = new ArrayList<>();
        // 保存一次结果
        StringBuilder track = new StringBuilder();
        //标记是否已遍历过
        boolean[] used = new boolean[chars.length];
        
        // 通过参数将它们传入核心函数
        backtrack(chars, used, track, res);
        return res;
    }

    // 回溯算法核心函数（参数较多）
    void backtrack(char[] chars, boolean[] used, StringBuilder track, List<String> res) {
        // base case，到达叶子节点
        if (track.length() == chars.length) {
            res.add(track.toString());
            return;
        }

        // 回溯算法标准框架
        for (int i = 0; i < chars.length; i++) {
            // 剪枝条件：跳过已使用字符或相同字符的重复分支
            if (used[i] || (i > 0 && chars[i] == chars[i-1] && !used[i-1])) {
                continue;
            }
            
            // 做选择
            used[i] = true;
            track.append(chars[i]);
            
            // 进入下一层回溯树
            backtrack(chars, used, track, res);
            
            // 撤销选择
            track.deleteCharAt(track.length() - 1);
            used[i] = false;
        }
    }
}

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

非递归

此方法算法理解难度较大，非标准解法

用字典序生成下一个排列的算法：

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

public class StringPermutation {
    public ArrayList<String> permutation(String str) {
        ArrayList<String> 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[i] >= chars[i + 1]) {
                i--;
            }
            if (i < 0) break; // 已是最大排列
            
            int j = chars.length - 1;
            // 找到第一个大于chars[i]的字符
            while (chars[j] <= chars[i]) {
                j--;
            }
            
            swap(chars, i, j);
            reverse(chars, i + 1, chars.length - 1);
            result.add(new String(chars));
        }
        
        return result;
    }
    
    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
    
    private void reverse(char[] chars, int start, int end) {
        while (start < end) {
            swap(chars, start++, end--);
        }
    }
}

• 时间复杂度​：O(n*n!)，每次生成下一个排列需要O(n)时间
• 空间复杂度​：O(n!)，结果存储空间