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

问题:查找出字符串中第一个只出现的字符。

思路:像这种统计次数之类的,通常用到哈希表,在Python中,dict是以哈希表存储的。利用哈希表,我们的时间复杂度是O(n),空间复杂度是O(1)(这是因为哈希表是有限大小的。)

 

from collections import OrderedDict


def search_1st_single_word(string):
    hashtable = OrderedDict()
    for index,w in enumerate(string):
        if hashtable.has_key(w):
            hashtable[w] = -1
        else:
            hashtable[w] = index
    print hashtable
    for key in hashtable:
        print key
        if hashtable[key] >= 0:
            return key,hashtable[key]
    return ValueError('no single char')



print search_1st_single_word('ssdddwgyy')

我之所以用了OrderedDict,是因为它可以保存插入的顺序,而普通的字典是无法保证插入的顺序的。因为我们是从头开始遍历的,列表下表也是按顺序排列的。

 

--------EOF---------
微信分享/微信扫码阅读