python - 仅包含 'a' 、 'b' 或 'c' 的子字符串

Question

我正在为 this problem. 编码

Maggu has just joined play school. His teacher taught him A,a,B,b,C,c. He is much fascinated with these letters and now he is looking only for those strings which contains these letters only. But as i said he is a little guy he cant calculate the number of such sub-strings alone. Find the number of such strings.

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 函数的时间消耗？我可以用其他代码替换它吗？

谢谢。

Answer 1

这是指数的原因是因为您针对不同的窗口长度(最多 len(string))迭代相同的字符串。这是正则表达式的一项工作，它只需遍历字符串即可查找至少一次连续包含字母 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

对于链接中显示的示例

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

2
6
4
21
0

<小时/>

如果您想自己实现 re.findall() 的功能，可以尝试以下操作。

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)