什么是此代码而不是double for循环（python）的更快版本？

一尘不染

什么是此代码而不是double for循环（python）的更快版本？

algorithm

当我将代码提交到（来自我的大学）对其进行更正的网站时，对于其标准而言，它太长了。这是代码：

def pangram(String):
    import string
    alfabet = list(string.ascii_lowercase)
    interpunctie = string.punctuation + "’" + "123456789"
    String = String.lower()
    string_1 = ""
    for char in String:                    
        if not char in interpunctie:
            string_1 += char
    string_1 = string_1.replace(" ", "")    
    List = list(string_1)
    List.sort()                            
    list_2 = []
    for index, char in enumerate(List):     
        if not List[index] == 0:
            if not (char == List[index - 1]):
                list_2.append(char)
    return list_2 == alfabet

def venster(tekst):
    pangram_gevonden = False
    if pangram(tekst) == False: 
        return None
    for lengte in range(26, len(tekst)):
        if pangram_gevonden == True:
            break
        for n in range(0, len(tekst) - lengte):
            if pangram(tekst[n:lengte+n]):
                kortste_pangram = tekst[n:lengte+n]
                pangram_gevonden = True
                break
    return kortste_pangram

因此，第一个函数（pangram）很好，它确定给定的字符串是否是pangram：它至少包含一次字母表中的所有字母。

第二个函数检查字符串（通常是较长的tekst）是否为字符组，如果是，则返回该tekst中最短的字符组（即使这不是正确的英语）。如果有两个长度相同的字母：返回最左边的一个。

在第二个函数中，我使用了double
for循环：第一个函数确定要检查的字符串的长度（26-len（string）），第二个函数使用此长度在每个可能的点遍历该字符串以检查是否这是一个pangram。一旦找到最短（也是最左边）的pangram，它就会脱离两个for循环。

但是，这（显然）仍然花费太长时间。因此，我想知道是否有人知道解决该第二功能的更快方法。它不一定必须带有for循环。

提前致谢

卢卡斯

阅读 236

2020-07-28

共1个答案

一尘不染

创建一个地图{letter; int}和activecount计数器。
让两个指标left和right设置他们0。

移动right索引。
如果l=s[right]为字母，则为地图键的增量值l。
如果值变为非零增量activecount。
继续直到activecount26

现在移动left索引。
如果l=s[left]为字母，则将地图键的值减小l。
如果值变为零-递减activecount并停止。

重新开始移动right索引，依此类推。

之间的差异很小left，并right同时
activecount==26在最短的全字母短句对应。

算法是线性的。

字符串示例代码，仅包含字母“ abcd”的小写字母。返回包含来自的所有字母的最短子字符串的长度abcd。不检查有效字符，没有经过全面测试。

import string
def findpangram(s):
    alfabet = list(string.ascii_lowercase)
    map = dict(zip(alfabet, [0]*len(alfabet)))
    left = 0
    right = 0
    ac = 0
    minlen = 100000

    while left < len(s):

        while right < len(s):
            l = s[right]
            c = map[l]
            map[l] = c + 1
            right += 1
            if c==0:
                ac+=1
                if ac == 4:
                    break
        if ac < 4:
            break
        if right - left < minlen:
            minlen = right - left

        while left < right:
            l = s[left]
            c = map[l]
            map[l] = c - 1
            left += 1
            if c==1:
                ac-=1
                break

        if right - left + 2 < minlen:
            minlen = right - left + 1
    return minlen

print(findpangram("acacdbcca"))

2020-07-28