Leet Code 解题笔记——字符串中的第一个唯一字符

题目描述：

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

解题思路：

# 从左往右对每个字符调用count方法，若计数为1，返回索引，若不为1，继续向后

if len(s) == 0:
    return -1
for i in range(len(s)):
    if s.count(s[i]) ==1:
        return i
    else :
        if i ==len(s)-1:
            return -1

方法应该是可行的，但是超时了……

然后构思了一个复杂度为n的算法。算法主要思想是建立一个以26个小写字母为键，以在s中的出现次数为值的字典。这个字典只需要遍历一遍s就可以得到。之后在字典中找到所有值为1的键，这些键在s字符串的位置可以通过s.find()方法找到，题目要求返回第一个不重复的字符串，所以只要返回这些键里在s中最靠前的那一个的索引就行了。

代码如下。

# 1. 建立以26个小写字母为键，每个值都是0的字典
keyslist = []
for i in range(26):
    keyslist.append(chr(i+97))
valuelist = [0]*26
d = dict(zip(keyslist, valuelist))

# 2. 遍历输入字符串，更新值
for i in range(len(s)):
    d[s[i]] +=1

# 3. 找到值为1的键
keys_1 = []  #keys_1是值为1的键的列表
for x in keyslist :
    c = d.get(x)
    if c ==1 :
        keys_1.append(x)
# 4. 确定这些键在s的位置，返回最靠前的一个
place = [] #是值为1的键在s中的位置的列表
if len(keys_1)==0 :
    return -1
else:
    for x in keys_1:
        place.append(s.find(x))
    
    return min(place)