剑指Offer50-第一个只出现一次的字符

兴趣爱好交流 每日一题
1

剑指Offer50-第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:


s = "abaccdeff"

返回 "b"

s = "" 

返回 " "

限制：

  • 0 <= s 的长度 <= 50000

来源：力扣（LeetCode）

链接：力扣

一解

利用词典存储字符的出现次数，最终返回次数为 1 的字符。


class Solution:

    def firstUniqChar(self, s: str) -> str:

        dic = {}

        for i in s:

            if i in dic:

                dic[i] += 1

            else:

                dic[i] = 1

        for i in s:

            if dic[i] == 1:

                return i

        return " "

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)，因为只有 26 个字母，即使 s 长度增加，也不影响大小

二解

使用字典，但存储的是“字母否重复”：


class Solution:

    def firstUniqChar(self, s: str) -> str:

        dic = {}

        for i in s:

            dic[i] = not i in dic

        

        for key, val in dic.items():

            if val: return key

        

        return " "