如何有效地计算字符串特定范围内给定字符的出现次数？

Question

给定一个未排序的字符串，例如“googol”。我想找出字符“o”在范围[1，3]中出现的次数。所以，在这种情况下，答案是1。你知道吗

但是，我的方法的复杂性为O（N^2）。我的方法的问题是复制数组需要O（N）时间。因此，我在寻找另一种更有效的方法。空间的复杂性对我来说并不重要。因为我正在学习字符串处理算法，如果我能自己实现这个算法就更好了。你知道吗

任何帮助都将不胜感激。你知道吗

我的方法。你知道吗

tmp = [0] * 26  # 26 alphabet
occurrences_table = []
tmp[ord(a_string[0])] += 1
occurrences_table.append(tmp)
for i in range(1, len(a_string)):
    temp = occurrences_table[i - 1]
    temp[ord(a_string[i])] += 1
    occurrences_table.append(temp)

Answer 1

如果可以使用标准库：

>>> from itertools import islice
>>> from collections import Counter
>>> Counter(islice('googol', 1, 3))
Counter({'o': 2})
>>> Counter(islice('googol', 0, 2))
Counter({'g': 1, 'o': 1})

（islice避免使用临时列表。）

如果要手动执行：

>>> s = 'googol'
>>> counter = dict()
>>> for i in range(0, 2):
...     if s[i] not in counter:
...         counter[s[i]] = 1
...     else:
...         counter[s[i]] += 1
... 
>>> counter
{'g': 1, 'o': 1}

关键是：使用dict。你知道吗

Answer 2

因为您不想使用counter并且希望自己实现它，所以可以通过使用字典来整理和加快代码的速度。你知道吗

a_string = "googol"
my_counter = {}
for c in a_string[:2]:
    my_counter[c] = my_counter.get(c, 0) + 1

这会给你：

{'o': 1, 'g': 1}

为了进一步解释它，a_string[:2]将字符串中的字符设置为索引2（'google'[:2]='go'），然后for c in a_string[:2]:在这两个字符上循环。你知道吗

在下一行中，my_counter.get(c, 0) + 1尝试获取键“c”（字符串中的单个字符）的字典值，如果该键存在，则返回其值；如果不存在，则返回0，并将递增的值添加回字典。你知道吗

---

编辑：

由于for循环，复杂性应该是O（n），因为dictionary.get()的复杂性是恒定的。你知道吗

我已经测量过了，对于像你这样的非常小的字符串，这个方法比Collections.Counter快8-10倍，但是对于非常大的字符串，它慢2-3倍。你知道吗

Answer 3

您可以使用^{}：

from collections import Counter
a_string = "googol"
occurrences = Counter(a_string[0:2])

结果是

Counter({'o': 1, 'g': 1})

请注意，数组切片对字符串有效。你知道吗