我写了一些代码来查找一个字符串中有多少个子字符串是字谜对。要找到的函数anagram(anagramSolution)的复杂度为O（N）。子字符串函数的复杂度小于N平方。但是，这里的代码就是问题所在。可以更优化吗？
for i in range(T):
x = raw_input()
alist = get_all_substrings(x)
for k, j in itertools.combinations(alist,2):
if(len(k) == len(j)):
if(anagramSolution(k,j)):
counter +=1
counterlist.append(counter)
counter = 0
该alist可以有上千项（子集）的。主要问题是循环。对所有项目进行迭代需要花费大量时间。有没有更快或更有效的方法来做到这一点？
将字符串的anagram类定义为每个字母在字符串中出现多少次的计数集合。例如，'banana'具有anagram class a: 3, b: 1, n: 2。如果两个字符串具有相同的字谜类，则它们是彼此的字谜。我们可以计算出每个字谜类中有多少个子字符串，然后通过计算(n choose 2)具有n个子字符串的每个字谜类来计算对数：
from collections import Counter
anagram_class_counts = Counter()
for substring in get_all_substrings(x):
anagram_class_counts[frozenset(Counter(substring).viewitems())] += 1
anagram_pair_count = sum(x*(x-1)/2 for x in anagram_class_counts.viewvalues())
frozenset(Counter(substring).viewitems()) 构建字符串的anagram类的可哈希表示。
Counter 进行迭代，并建立一个表示每个项目出现次数的映射，因此Counter(substring) 构建一个表示字符串的字谜类的映射。viewitems() 给出一组类似字母的集合：计数对，和frozenset 将其转换为可以用作字典键的不可变集合。这些步骤花费的时间与子字符串的大小成正比。平均而言，子字符串大约是整个字符串大小的三分之一，因此平均而言，处理每个子字符串需要O(len(x))时间。有O(len(x)**2)子字符串，因此处理所有子字符串需要O(len(x)**3)时间。
如果存在x具有相同字谜类的子字符串，则可以通过x*(x-1)/2多种方式将它们配对，因此sum将遍历每个字谜类的出现次数并计算对数。这需要O(len(x)**2)时间，因为它必须遍历每个字谜类一次，并且字谜类不能超过子字符串。
总的来说，该算法需要O(len(x)**3)时间，虽然并不理想，但是比原始算法要好得多。仍然有优化的空间，例如通过利用子串之间重叠的方式计算字谜类或使用更有效的字谜类表示来进行优化。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句