题⽬描述

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

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

思路及解答

递归回溯（使用Set去重）

看到题目，应该就知道要使⽤回溯了。

通过 ​回溯算法​ 生成所有排列，配合 ​剪枝条件​ 实现去重和字典序输出。关键步骤包括：

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

import java.util.ArrayList;
import java.util.Collections;

public class StringPermutation {
    public ArrayList permutation(String str) {
        ArrayList result = new ArrayList();
        if (str == null || str.length() == 0) {
            return result;
        }
        
        char[] chars = str.toCharArray();
        permute(chars, 0, result);
        Collections.sort(result); // 按字典序排序
        return result;
    }
    
    private void permute(char[] chars, int begin, ArrayList result) {
        if (begin == chars.length - 1) {
            result.add(new String(chars));
            return;
        }
        
        for (int i = begin; i 

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

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

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

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

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); // 先排序便于去重
        boolean[] used = new boolean[chars.length];
        backtrack(chars, used, new StringBuilder(), result);
        return result;
    }
    
    private void backtrack(char[] chars, boolean[] used, 
                         StringBuilder path, ArrayList result) {
        if (path.length() == chars.length) {
            result.add(path.toString());
            return;
        }
        
        for (int i = 0; i  0 && chars[i] == chars[i-1] && !used[i-1])) {
                continue;
            }
            
            used[i] = true;
            path.append(chars[i]);
            backtrack(chars, used, path, result);
            path.deleteCharAt(path.length() - 1); // 回溯
            used[i] = false;
        }
    }
}

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

非递归

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

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

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

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[i] >= chars[i + 1]) {
                i--;
            }
            if (i 

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

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top