如何在字符串的特定範圍內高效地計算給定字符的出現次數？給定一個未分類的字符串，例如：

「天文數字」。我想在範圍[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

如何在字符串的特定範圍內高效地計算給定字符的出現次數？給定一個未分類的字符串，例如：

回答

相關問題