时间戳

首页 > 解决方案 > 先找到不重复的字符

python - 先找到不重复的字符

问题描述

问题：

给定一个由小英文字母组成的字符串 s，找到并返回其中不重复字符的第一个实例。如果没有这样的字符，返回'_'。

例子

对于s = "abacabad"，输出应该是 firstNotRepeatingCharacter(s) = 'c'。

这是我到目前为止所拥有的，但它太慢了。如何使运行时间更快？谢谢。

def firstNotRepeatingCharacter(s):
    char = set(s)
    for i in range(len(s)):
        if s.count(s[i]) == 1:
            return s[i]
    return "_"

标签： python

解决方案

您可以使用collections.Counter以线性时间计算字符，然后与next一起过滤结果，如下所示：

from collections import Counter


def firstNotRepeatingCharacter(s):
    counts = Counter(s)
    return next((ch for ch in s if counts[ch] < 2), "_")


print(firstNotRepeatingCharacter("abacabad"))

输出

c

或者简单地使用字典（不需要导入）：

counts = {}
for ch in s:
    counts[ch] = counts.get(ch, 0) + 1

return next((ch for ch in s if counts[ch] < 2), "_")

两种方法在输入字符串的长度上都是线性的，您当前的方法是唯一字符的数量O(k*s)在哪里。k

推荐阅读