有重复字符串的排列组合
难度:
标签:
题目描述
Write a method to compute all permutations of a string whose characters are not necessarily unique. The list of permutations should not have duplicates.
Example1:
Input: S = "qqe" Output: ["eqq","qeq","qqe"]
Example2:
Input: S = "ab" Output: ["ab", "ba"]
Note:
- All characters are English letters.
1 <= S.length <= 9
代码结果
运行时间: 22 ms, 内存: 16.0 MB
/*
* 思路:
* 1. 使用递归生成字符串的所有排列。
* 2. 利用Java Stream API处理结果集合和转换操作。
*/
import java.util.*;
import java.util.stream.Collectors;
public class PermutationStream {
public List<String> permutation(String S) {
Set<String> result = new HashSet<>();
permute(S.toCharArray(), 0, result);
return result.stream().collect(Collectors.toList());
}
private void permute(char[] chars, int index, Set<String> result) {
if (index == chars.length) {
result.add(new String(chars));
return;
}
for (int i = index; i < chars.length; i++) {
swap(chars, index, i);
permute(chars, index + 1, result);
swap(chars, index, i); // 回溯
}
}
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) {
PermutationStream solution = new PermutationStream();
System.out.println(solution.permutation("qqe"));
System.out.println(solution.permutation("ab"));
}
}解释
方法:
此题解采用了递归回溯的方法来生成字符串的所有排列组合。首先，对给定字符串的每一个字符，将其作为当前排列的第一个字符，然后对剩余的字符再进行排列。为了避免重复的排列，通过检查当前字符是否在它前面的字符中出现过来跳过重复的情况。这样可以确保每个字符在每个位置上只被使用一次。每一层递归都会减少一个字符，直到字符串为空，此时返回包含空字符串的数组。
时间复杂度:
O(n * n!)
空间复杂度:
O(n!)
代码细节讲解
🦆
在递归回溯方法中，你是如何确保不会对已经处理过的字符进行重复处理的？
▷🦆
你提到通过检查当前字符是否在它前面的字符中出现过来跳过重复，这种方法在所有情况下都有效吗，还是有可能遗漏某些重复排列？
▷🦆
对于字符串中的每一个字符，你选择将其作为当前排列的第一个字符，然后对剩余字符进行排列。这种方法有没有考虑字符的频率或者其他属性来优化性能？
▷