计算给定字符串的子串数，这些子串是变音图

Question

我需要找到给定字符串的所有子字符串的变音图。我使用以下代码找到给定字符串的所有可能的子字符串：

def anagrams(string):
    # abba
    subs = [string[i:j+1] for i in range(len(string)) for j in range(i, len(string))]
    # ['a', 'ab', 'abb', 'abba', 'b', 'bb', 'bba', 'b', 'ba', 'a']

我想从这个列表中找到等长的子串，如果它们是字谜。有什么想法吗？在

Answer 1

如果两个字符串是字谜，它们的长度必须相同，您可以直接用一个简单的嵌套for循环来测试它们。在

为了检查两个字符串是否是字谜，^{}很有用：它统计iterable中每个不同元素的出现次数，因此两个字符串si和{}是字谜当且仅当Counter(si) == Counter(sj)。在

from collections import Counter

def anagrams(string):
    subs = [string[i:j+1] for i in range(len(string)) for j in range(i, len(string))]
    counters = list(map(Counter, subs))
    total = 0

    for i, ci in enumerate(counters):
        for j, cj in enumerate(counters):
            if i != j and ci == cj:
                total += 1

    return total

Answer 2

与@MarcoBonelli answer一样，您可以使用collections.Counter来创建一个字符串的表示形式，当且仅当这些字符串是彼此的换位符时，该字符串才会相等，例如：

'bba' -> ('b', 2), ('a', 1)
'abb' -> ('b', 2), ('a', 1)

不必执行嵌套的for循环并检查每对，您可以使用字典对具有相同计数器表示的字符串进行分组，并使用单个循环：

^{pr2}$

输出

[['abb', 'bba'], ['b', 'b'], ['ab', 'ba'], ['a', 'a']]

在输出中，子列表对应于字符串组，这些字符串是彼此的anagram。要使用字典中的计数器，您必须将项目转换为frozenset。最后，这种方法的复杂度是O（n），其中n是子串的数目。在