题目描述:在一个字符串(0 <= 字符串长度 <= 10000,全部由字母组成)中找到第一个只出现一次的字符, 并返回它的位置, 如果没有则返回 -1(需要区分大小写)。
Solutions
首先快速写一下 $O(n^2)$ 的暴力解法:
# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if s is None or s is '':
return -1
for i, c in enumerate(s):
count = 0
for d in s:
if c == d:
count += 1
if count == 1:
return i
return -1
还有一种利用 Python 特性的作弊式解法:
# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if not s or len(s)<=0:
return -1
for i in s:
if s.count(i)==1:
return s.index(i)
return -1
比较高效的办法是利用哈希表的方式来找次数,两次遍历字符串,第一次统计字符次数,第二次找到第一个出现一次的字符:
# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
if not s or len(s)<=0:
return -1
char_dict = {}
for c in s:
if c in char_dict:
char_dict[c] += 1
else:
char_dict[c] = 1
for i, c in enumerate(s):
if char_dict[c] == 1:
return i
return -1