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

Question

给定一个未排序的字符串，例如“咕咕”。我想查找范围内字符“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

因为您不想使用 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，并且无论哪种方式都将增加的值添加回字典。

---

编辑:

由于 dictionary.get() 的复杂度是常数，因此由于 for 循环，复杂度应该仅为 O(n)。

我已经对其进行了测量，对于像您这样的非常小的字符串，此方法比 Collections.Counter 快 8-10 倍，但对于非常大的字符串，它会慢 2-3 倍。