在字符串中找到第一个不重复的字符

Question

我看到一个面试问题，要求写一些代码来解决以下内容：

写一个高效的函数，找出字符串中第一个没有重复的字符。比如，在“total”这个词中，第一个没有重复的字符是'o'；而在“teeter”这个词中，第一个没有重复的字符是'r'。讨论一下你这个算法的效率。

我用Python想出了这个解决方案；不过，我相信还有更优雅的方法可以做到这一点。

word="googlethis"
dici={}

#build up dici with counts of characters
for a in word:
    try:
        if dici[a]:
            dici[a]+=1
    except:
        dici[a]=1

# build up dict singles for characters that just count 1 

singles={}
for i in dici:
    if dici[i]==1:
        singles[i]=word.index(i)

#get the minimum value

mini=min(singles.values())

#find out the character again iterating...

for zu,ui in singles.items():
    if ui==mini:
        print zu 

有没有更简洁和高效的答案呢？

Answer 1

sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]

我觉得，或者说DSM也很简洁。

next(c for c in word if word.count(c) == 1) 

这在效率上稍微更高一点。

>>> word = "teeter"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'r'
>>> word = "teetertotter"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'o'
>>> word = "teetertotterx"
>>> sorted(word,key=lambda x:(word.count(x),word.index(x)) )[0]
'o'

Answer 2

from collections import defaultdict
word="googlethis"
dici=defaultdict(int)

#build up dici with counts of characters
for a in word:
    if dici[a]:
        dici[a]+=1
for a in word:
    if didic[a] < 2:
        return a

那样不行吗？

Answer 3

In [1033]: def firstNonRep(word):
   ......:     c = collections.Counter(word)
   ......:     for char in word:
   ......:         if c[char] == 1:
   ......:             return char
   ......:         

In [1034]: word="googlethis"

In [1035]: firstNonRep(word)
Out[1035]: 'l'

编辑: 如果你想实现相同的功能，但不想使用像 Counter 这样的辅助工具：

def firstNonRep(word):
    count = {}
    for c in word:
        if c not in count:
            count[c] = 0
        count[c] += 1
    for c in word:
        if count[c] == 1:
            return c