我编写了一些代码来查找字符串中有多少个子串是字谜对。要查找的函数anagram(anagramSolution)
复杂度为 O(N)。 substring函数的复杂度小于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
The alist
可以有数千个项目(子集)。主要问题是循环。迭代所有项目需要花费大量时间。有没有更快或更有效的方法来做到这一点?
定义字谜类字符串中每个字母在字符串中出现次数的计数集。例如,'banana'
有字谜类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)
time.
如果有x
具有相同字谜类的子串,它们可以配对x*(x-1)/2
方式,所以sum
遍历每个字谜类的出现次数并计算对的数量。这需要O(len(x)**2)
时间,因为它必须遍历每个字谜类一次,并且字谜类的数量不能多于子字符串。
总的来说,该算法需要O(len(x)**3)
时间,虽然不是很好,但比原来的好很多。对此仍有优化的空间,例如通过利用子串之间重叠的方式计算字谜类,或者使用更有效的字谜类表示。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)