题目描述:在一个字符串(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

References

  1. 035. 第一个只出现一次的字符