Permutations With Duplicates

作者 QIFAN 日期 2016-10-21
Permutations With Duplicates

Source: Cracking the Code Interview 8.8


Description

Write a method to compute all permutations of a string whose
characters are not necessarily unique. The list of permutations should not have duplicates.

* Permutation:字符组成完全一样但顺序不一样的字符串。

思路

简单粗暴的方式就是找出所有的排列组合然后若已经存在则删去。复杂度为 $O(n!)$,显然不是最优的。

permutation 会重复的原因就是因为有重复的字符,所以首先想到的是建一个 map ,存下每个字符的出现情况。
假设字符串 aabcc ,则 map 是:
a->2 | b->1 | c->2
如果要用到动态规划,我们就要考虑 base case,normal case。

对于 aabcc 的 permutation 肯定是 a 或者 b 或者 c 开头的,因此:

P(a->2 | b->1 | c->2) = {a + P(a->1 | b->1 | c->2)} +
{b + P(a->2 | b->0 | c->2)} +
{c + P(a->2 | b->1 | c->1)}
P(a->1 | b->1 | c->2) = {a + P(a->0 | b->1 | c->2)} +
{b + P(a->1 | b->0 | c->2)} +
{c + P(a->1 | b->1 | c->1)}

将字符分为两部分,前缀与剩下的,所以每次运算都会抛出一种字符,并将其加入前缀,剩下的字符个数自然减1

Base case : 当剩余个数为 0 时,前缀就是该字符串的一种 permutation 。

Solution

List<String> perms(String s) {
HashMap<Character, Integer> map = new HashMap<>();
// 遍历字符串
for (int i = 0; i < s.length(); i++) {
if(!map.contains(s.charAt(i))) {
map.put(s.charAt(i), 1);
} else {
map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
}
}
ArrayList<String> result = new ArrayList<>();
perms(map, result, "", s.length());
return result;
}
void perms(HashMap<Character, Integer> map, ArrayList<String> result, String pre, int remaining) {
// base case,如果没有剩余字符则将pre加入result
if(remaining == 0) result.add(pre);
else {
// 遍历map,递归生成不同的permutation
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
if (entry.getValue() == 0) {
continue;
}
List<Integer> newPerm = new ArrayList<>(perm);
map.put(entry.getKey(), entry.getValue() - 1);
newPerm.add(entry.getKey());
getPerms(map, res, newPerm, remain - 1);
map.put(entry.getKey(), entry.getValue() + 1);
}
}
}

分析

对于有 M 个不同字符长度为 N 的字符串,每个节点都有当前 map 的 key 数量个分支,最大为 M ,一共有 N 层,因此,若 M=N , 则花费 $O(N!)$,而 M < N ,时间复杂度必然小于 $O(N!)$ ,具体则取决于字符串中重复字符的频度。