时间戳

首页 > 解决方案 > 用于检查字谜数量的 Python 优化循环

python - 用于检查字谜数量的 Python 优化循环

问题描述

我正在尝试解决一个提供字符串作为输入并给出可能的字谜数量作为输出的问题。这可以使用字典来解决，但我只能考虑 for 循环和字符串索引。 

count = 0
    for i in range(1,len(s)):
        for j in range(0,len(s)):
            for k in range(j+1,len(s)):
                if(k+i>len(s)):
                    continue
                # print(list(s[j:j+i]),list(s[k:k+i]),j,j+i,k,k+i)
                if(sorted(list(s[j:j+i]))==sorted(list(s[k:k+i]))):
                    count +=1         
    return count

我已经编写了这么多，并尝试使用 k+i 进行优化。有人可以告诉我在不丢失逻辑的情况下优化代码的其他技术吗？由于较大的字符串超时，代码不断终止。我应该sorted用其他东西替换函数吗？

标签： pythonoptimization

解决方案

如果每个字母都是唯一的，则字谜的数量将n!与n字符串的长度一样（例如 law has 3!=6）。如果一个给定的字母被重复两次（例如wall），那么你得到的答案是你应该得到的答案的两倍（因为类似w-(second l)-(first l)-a的东西实际上与类似的东西没有区别w-(first l)-(second l)-a）。事实证明，如果一个字母被重复k多次（对于in 中k的字母是 2 ），则多算 1 倍。对于每个重复的字母都是如此。"l"walln!k!

所以要获得字谜的数量，你可以这样做：

letter_counts = get_letter_counts(s) #returns something like [1, 1, 2] when given wall, since there is one w, one a, two ls
n_anagrams = factorial(len(s))

#account for overcounts
for letter_count in letter_counts:
    n_anagrams /= factorial(letter_count)

return n_anagrams

实施factorial并get_letter_counts留给读者作为练习:-)。注意：请注意重复的字母可能会出现不止一次，而且并不总是彼此相邻。例如：“aardvark”应该为“a”返回 3，为“r”返回 2，为其他所有内容返回 1。

推荐阅读