在Python中删除字符串中的重复项

Question

删除字符串中所有重复项的有效算法是什么？

例如:aaaabbbccdbdbcd

要求的结果:abcd

Answer 1

您使用哈希表来存储当前发现的密钥(访问O(1)),然后循环遍历该数组.如果一个字符在哈希表中,则将其丢弃.如果没有将它添加到哈希表和结果字符串中.

总体而言:O(n)时间(和空间).

天真的解决方案是在处理每个字符时搜索字符是结果字符串.那个O(n ²).

Answer 2

在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 3

这与以下问题密切相关:用无限输入检测重复.

根据您的输入,哈希表方法可能不是最佳的.哈希表有一定的开销(桶,入口对象).与实际存储的char相比,这是一个巨大的开销.(如果您的目标环境是Java,则更糟糕的是因为HashMap属于类型Map<Character,?>.)由于冲突,Hashtable访问的最坏情况运行时是O(n).

您只需要8kb表示普通BitSet中的所有2字节unicode字符.如果您的输入字符集受到更多限制或使用压缩的BitSet(只要您有稀疏的BitSet),则可以优化此选项.对于BitSet,运行时性能将是有利的,它是O(1).