在面试中，字符串的全排列问题是一个经典的面试题，要求生成一个字符串的所有全排列，且去重。这个问题可以通过回溯法（Backtracking）来实现，同时利用一个 HashSet 来避免重复的排列。下面我会详细说明思路、时间复杂度和空间复杂度，并给出完整的 Java 代码。
1. 问题理解
给定一个字符串，要求输出该字符串的所有可能的排列（排列需要去重），并且考虑到字符串可能包含重复字符，结果中的排列也应该去重。
2. 思路分析
使用回溯法生成所有可能的排列。回溯法的核心思想是递归地交换字符，在每一层递归中交换一个字符到当前位置，并继续处理剩下的部分。为了避免重复的排列，可以在递归过程中使用一个 HashSet 来记录已经生成的排列。
步骤：
- 排序：首先对字符串进行排序，可以帮助我们提前跳过重复字符。例如，如果字符串是 “AAB”，排序后是 “AAB”，这样我们可以确保在递归过程中只处理一遍相同的字符。
- 回溯法生成排列：在递归中，每次交换一个字符到当前位置，然后递归处理剩余部分。
- 在交换字符时，检查该字符是否已经在当前位置的前面出现过，如果出现过则跳过。
- 去重：为了避免重复的排列结果，我们可以使用一个
HashSet 来记录所有已生成的排列（字符串形式）。
3. 时间复杂度和空间复杂度
- 时间复杂度：生成排列的总数是
n!，其中 n 是字符串的长度。每次递归交换的时间复杂度是 O(n)，因此总体时间复杂度为 O(n * n!)。 - 空间复杂度：空间复杂度主要由递归栈和存储结果的集合组成。递归栈的深度最大为
n，存储结果的集合最多保存 n! 个排列，因此空间复杂度为 O(n * n!)。
4. Java代码实现
import java.util.*;
public class Solution {
public List<String> permuteUnique(String s) {
// 用一个列表保存结果
List<String> result = new ArrayList<>();
// 将字符串转换为字符数组并排序，排序后有助于去重
char[] chars = s.toCharArray();
Arrays.sort(chars);
// 结果集合，用来存储去重后的排列
Set<String> set = new HashSet<>();
// 通过回溯法生成排列
backtrack(chars, 0, result, set);
// 将集合转换为列表返回
return new ArrayList<>(set);
}
private void backtrack(char[] chars, int index, List<String> result, Set<String> set) {
// 当到达字符数组的最后一位时，生成一个排列
if (index == chars.length) {
String permutation = new String(chars);
set.add(permutation); // 将当前排列加入结果集合
return;
}
// 遍历每个字符
for (int i = index; i < chars.length; i++) {
// 如果当前字符和前一个字符相同，跳过（避免重复排列）
if (i > index && chars[i] == chars[i - 1]) {
continue;
}
// 交换字符
swap(chars, i, index);
// 递归处理
backtrack(chars, index + 1, result, set);
// 回溯，恢复交换前的状态
swap(chars, i, index);
}
}
// 辅助函数：交换字符数组中的两个字符
private void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "AAB";
List<String> result = solution.permuteUnique(s);
for (String str : result) {
System.out.println(str);
}
}
}
5. 解释代码
- permuteUnique 方法：首先将输入字符串转换为字符数组，并对字符数组进行排序。然后调用回溯方法
backtrack 来生成所有的排列。 - backtrack 方法：这是回溯法的核心部分。在每一层递归中，遍历当前位置后面的所有字符，交换并递归处理。
- swap 方法：用于交换字符数组中的两个字符。
- 去重：通过
Set 来存储所有排列，确保没有重复的排列结果。
6. 举例说明
对于输入字符串 "AAB"：
- 排序后得到
['A', 'A', 'B']。 - 通过回溯法生成所有排列并使用
HashSet 去重，最终得到 [ "AAB", "ABA", "BAA" ]。
7. 测试
在 main 方法中，我们测试了输入 "AAB"，并打印了结果。你可以替换 s 的值来测试其他输入。
8. 总结
这道题通过回溯法可以有效生成所有排列，并且通过排序和 Set 来保证去重。时间复杂度是 O(n * n!)，空间复杂度是 O(n * n!)，适合用来处理字符串全排列的相关问题。