蟒蛇 - 只包含 'A'， 'B' 或 'C'

Maggu子串剛剛加盟在玩中學。他的老師教他A，A，B，B，C，C。他對這些信件非常着迷，現在他只查看只包含這些字母的字符串。但正如我所說他是一個小傢伙，他不能單獨計算這種子串的數量。找到這樣的字符串的數量。

def substrings(string): 
    for size in range(1, len(string)+1): 
     for index in range(len(string)-size+1): 
      yield string[index:index+size] 

l = [] 

for x in range(int(raw_input())): 
    l.append(raw_input().lower()) 

not_ = 'defghijklmnopqrstuvwxyz' 

for string in l: 
    count = 0 
    for substr in substrings(string): 
     if all(letter not in substr for letter in not_): 
      count = count + 1 
    print(count)

我意識到，我們可以減少爲小寫的問題。我編寫了代碼，但對於大型字符串來說效率不高。大的意思是特大字符串。我意識到這是佔用了大量時間的substrings函數。我如何減少substrings函數的時間消耗？我可以用其他代碼替換它嗎？

謝謝。

來源

2016-04-06 Some Name

python 2.的一個改進U應該使用'xrange'而不是'range'。這是更大的表現 – qvpham

@julivico好主意。 Python 2中'xrange'的速度遠遠超過'range'。 –

你想用x中的代碼做什麼（int（raw_input（）））： l.append（raw_input（）。lower ））' – qvpham

這是指數級的原因是因爲您針對不同的窗口長度（最多len（字符串））迭代相同的字符串。這是正則表達式的一個工作，它將簡單地通過一個字符串來查找任何包含字母a，b，c，A，B和C的序列，至少一次。

找到這些序列後，可以計算它們的算術級數來計算每個包含的子串數量。要理解爲什麼我們必須使用算術級數，考慮我們在大串中找到序列'abc'。這個序列的實際子串是'a'，'ab'，'abc'，'b'，'bc'和'c'。基本上，對於長度爲n的字符串，我們可以從第一個字母開始構建n個子字符串，從第二個字母開始n-1個子字符串，...和從最後一個字母開始的1個子字符串。

import re 

def count_substrings(string): 
    found = re.findall('[a-cA-C]+', string) 
    count = 0 
    for f in found: 
     length = len(f) 
     count += length * (length + 1)/2 
    return count

。如果你想實現什麼re.findall()做你自己，你可以試試下面的鏈接

>>> strings = ['AXa', 'ABC', 'AXBC', 'AaBbCc', 'XxYyZz'] 
>>> for s in strings: 
... print(count_substrings(s)) 

2 
6 
4 
21 
0

所示的例子。

found = [] 
substring = '' 
for s in string: 
    if s in 'abcABC': 
     substring += s 
    else: 
     # if we had a sequence going, it just ended, so add it to our found list 
     if substring: 
      found.append(substring) 
      substring = '' 
# make sure to append the last sequence we had been working on 
if substring: 
    found.append(substring)

來源

2016-04-06 11:36:21 Reti43

蟒蛇 - 只包含 'A'， 'B' 或 'C'

回答

相關問題