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

• 2017-11-17
• 作者： 王海波
• 分类：算法
• 访问量：1421

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

思路：像这种统计次数之类的，通常用到哈希表，在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---------
微信分享/微信扫码阅读