Permutations with Dups: Write a method to compute all permutations of a string whose charac ters are not necessarily unique. The list of permutations should not have duplicates.
Hints: #161, #190, #222, #255
解法1
还是用8.7 Permutations without Dups的prefix法来做，查看prefix是否被用过，如果用过则跳过：
1
2
3
4
5
6
7
8
9
10
11
|
P(, aab)
P(a, ab)
P(aa, b)
P(aab, ) <- 最终结果
P(ab, a)
P(aba, ) <- 最终结果
P(a, ab) <- X相同prefix
P(b, aa)
P(ba, a)
P(baa, ) <- 最终结果
P(ba, a) <- X相同prefix
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public List<String> permute(String str) {
List<String> result = new ArrayList<>();
permute(new StringBuilder(), new StringBuilder(str), result);
return result;
}
public void permute(StringBuilder prefix, StringBuilder post, List<String> permutations) {
if (post.length() == 0) {
permutations.add(prefix.toString());
return;
}
Set<String> prefixes = new HashSet<>();
for (int i = 0; i < post.length(); i++) {
char c = post.charAt(i);
prefix.append(c);
post.deleteAt(i);
if (!prefixes.contains(prefix)) {
prefixes.add(prefix);
permute(prefix, post, permutations);
}
prefix.deleteAt(prefix.length() - 1);
post.insert(c, i);
}
}
|
空间复杂度：就是计算HashSet中存了多少个字符。以不重复的时候计算，因为之前的调用返回后都归还了空间，我们只看最后一次调用整个两条上用到的空间：
1
2
3
4
5
6
7
|
P( , abc)
P(a, bc)
P(b, ac)
P(c, ab)
P(ca, b)
P(cb, a)
P(cba, )
|
用了：1个3字符，2个2字符，3个1字符 ，总共10个字符。
换成公式等于：
1
2
3
|
缓存的字符数 = 1 * n + 2 * (n - 1) + 3 * (n - 2) + ... + (n - 2) * 3 + (n - 1) * 2 + n * 1
= 2 * (n + 2n + 3n + ... + (n/2) * n) - 2 * (2*1 + 3*2 + 4*3 + 5*4)
= 大致上是O(n^3)
|
解法2
这个解法是答案里看来的，比较难以理解。大致思想是你不管重复的字符，你只需要知道有多少个unique字符，并且它们的计数是多少。
然后在unique字符中取出
- 取出一个字符，添加到prefix中，将其计数-1。如果这个字符计数为0则跳过。
- 在剩余字符里，重复第1步
- 直到prefix长度等于字符串长度，那么prefix就是一个permutation
下面是一个举例：
1
2
3
4
5
6
7
8
9
10
11
|
Input : aab
charCount : a=2, b=1
P(, aab)
P(a, ab) a=1, b=1
P(aa, b) a=0, b=1
P(aab, ) a=0, b=0 <- 最终结果
P(ab, a) a=1, b=0
P(aba, ) a=0, b=0 <- 最终结果
P(b, aa) a=2, b=0
P(ba, a) a=1, b=0
P(baa, ) a=0, b=0 <- 最终结果
|
这个办法的精髓是：每次是取出一个unique字符，所以就不存在同一字符在同一index出现两次的情况。
可以对比解法1做法：
1
2
3
4
5
6
7
8
9
10
11
|
P(, aab)
P(a, ab)
P(aa, b)
P(aab, )
P(ab, a)
P(aba, )
P(a, ab) <- a在index=0里再一次出现了
P(b, aa)
P(ba, a)
P(baa, )
P(ba, a) <- X相同prefix
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
public List<String> permute(String str) {
List<String> result = new ArrayList<>();
Map<Char, Integer> charCount = makeCharCount(str);
permute(charCount, "", str.length(), result);
return result;
}
private Map<Char, Integer> makeCharCount(String str) {
Map<Char, Integer> result = new HashMap<>();
for (int i = 0; i < str.length; i++) {
char c = str.charAt(i);
Integer count = result.get(c);
if (count == null) {
result.put(c, 0);
count = 0;
}
result.put(c, count + 1);
}
return result;
}
private void permute(Map<Char, Integer> charCount, String prefix, int remaining, List<String> permutations) {
if (remaining == 0) {
permutations.add(prefix);
}
for (Char c : charCount.keySet()) {
int count = charCount.get(c);
if (count > 0) {
charCount.put(c, count - 1);
permute(charCount, prefix + c, remaining - 1, permutations);
// 恢复计数，给当前index的下一次取的是别的字符，自己的计数-1要恢复
charCount.put(c, count);
}
}
}
|
空间复杂度：O(n)，n是字符串长度。
评论