我编写了一些代码来查找字符串中有多少个子字符串是anagram对.找到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类a：3,b：1,n：2.如果两个字符串具有相同的anagram类,则它们是彼此的字谜.我们可以计算每个anagram类中字符串的子串数,然后通过计算(n选择2)为每个具有n个子串的anagram类计算对的数量：

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采用iterable并构建一个映射,表示每个项目出现的次数,所以
> Counter(substring)构建一个表示字符串的anagram类的映射.
> viewitems()给出了一个类似于集合的集合：count对,和
> frozenset将其转换为可用作dict键的不可变集.

这些步骤共同花费时间与子串的大小成比例;平均而言,子串大约是整个字符串大小的三分之一,因此平均而言,处理每个子字符串需要O(len(x))时间.有O(len(x)** 2)子串,因此处理所有子串需要O(len(x)** 3)时间.

如果存在具有相同anagram类的x子串,则它们可以以x *(x-1)/ 2方式配对,因此总和将计算每个anagram类的出现次数并计算对的数量.这需要O(len(x)** 2)时间,因为它必须经过每个anagram类一次,并且不能有比字串更多的anagram类.

总的来说,这个算法需要O(len(x)** 3)时间,这不是很好,但它比原来好很多.仍然有优化这一点的空间,例如通过利用子串之间的重叠或使用更有效的anagram类表示来计算anagram类.