在Python中去除字符串重复字符

Question

什么是高效的算法来去除字符串中的所有重复字符？

比如说：aaaabbbccdbdbcd

我们想要的结果是：abcd

Answer 1

在Python中

>>> ''.join(set("aaaabbbccdbdbcd"))
'acbd'

如果需要保持顺序

>>> q="aaaabbbccdbdbcd"                    # this one is not
>>> ''.join(sorted(set(q),key=q.index))    # so efficient
'abcd'

或者

>>> S=set()
>>> res=""
>>> for c in "aaaabbbccdbdbcd":
...  if c not in S:
...   res+=c
...   S.add(c)
... 
>>> res
'abcd'

或者

>>> S=set()
>>> L=[]
>>> for c in "aaaabbbccdbdbcd":
...  if c not in S:
...   L.append(c)
...   S.add(c)
... 
>>> ''.join(L)
'abcd'

在python3.1中

>>> from collections import OrderedDict
>>> ''.join(list(OrderedDict((c,0) for c in "aaaabbbccdbdbcd").keys()))
'abcd'

Answer 2

这个内容和这个问题很相关：检测无限输入中的重复。

使用哈希表的方法可能不是最优的，具体要看你的输入数据。哈希表有一定的开销（比如桶和条目对象）。相比于实际存储的字符，这个开销是很大的。（如果你使用的环境是Java，那就更糟糕了，因为HashMap的类型是Map<Character,?>。）在最坏的情况下，访问哈希表的时间复杂度是O(n)，这是因为可能会发生冲突。

你只需要8kb就可以表示所有2字节的unicode字符，使用一个普通的BitSet就可以。如果你的输入字符集比较有限，或者使用压缩的BitSet（只要你有一个稀疏的BitSet），这可以进一步优化。对于BitSet来说，运行时性能是非常好的，时间复杂度是O(1)。

Answer 3

你可以用一个哈希表来存储已经找到的字符，这样查找的速度很快，基本上是O(1)的时间。然后你再遍历数组。如果某个字符在哈希表里，就把它丢掉；如果不在，就把它加到哈希表和结果字符串里。

总的来说，这个方法的时间和空间复杂度都是O(n)。

而简单的方法是每处理一个字符，就去结果字符串里查找这个字符，这样的效率就比较低，大约是O(n²)。