如何在字符串的特定范围内高效地计算给定字符的出现次数？给定一个未分类的字符串，例如：

“天文数字”。我想在范围[1，3]中找到字符“o”的出现次数。因此，在这种情况下，答案将是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)

来源

2017-04-18 Kaiwei Luo

检查[集合。计数器（https://docs.python.org/2/library/collections.html#collections.Counter）。您可以使用[切片]（https://docs.python.org/2.3/whatsnew/section-slices.html）来处理特定范围的字符串。 – umutto

@umutto。但这就像我正在学习一些字符串处理算法。所以我想自己实现这个算法。 –

@kevinnnluo - 你真的应该在你原来的问题中提到这种限制。 –

由于您不想使用并希望自己实现它，因此可以使用字典对代码进行整理并加快速度。

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]得到字符，直到达到您的字符串（'google'[:2] = 'go'）和for c in a_string[:2]:环比那些2个字符指数2。

在下一行中，my_counter.get(c, 0) + 1会尝试获取键“c”（字符串中的单个字符）的字典值，如果它存在，则返回其值，如果不返回0，并且任何一种方法都会将增加的值回到字典。

编辑：

复杂性应该只是为O（n）由于在for循环以来的dictionary.get()复杂是恒定的。

我测量过它，对于像你这样的非常小的字符串，这种方法比Collections.Counter快8-10倍，但是对于非常大的字符串，它速度要慢2-3倍。

来源

2017-04-18 08:24:01 umutto

如果你可以使用标准库：

>>> 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。

来源

2017-04-18 08:13:41 phg

我认为他的'范围[1,3]' - 注记从位置1开始计数直到排除位置3的字符 - 在python中非常有效[0：2]。 –

感谢您的回答。因为范围是[1,3]，子字符串是“去”，只有一个“o”。但这就像我正在学习字符串处理算法，所以我想自己实现它。 –

是啊，我意识到，当我看到你回答;） – phg

你可以使用一个Counter：

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

导致

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

注意，阵列切片上串的作品。

来源

2017-04-18 08:13:49

如何在字符串的特定范围内高效地计算给定字符的出现次数？给定一个未分类的字符串，例如：

回答

相关问题