使用 python 中的对称差异从两个字符串制作 Anagrams 的计算成本

Question

给定两个长度为 |a| 的字符串 a 和 b和|b|，计算总共应该删除的元素数量，使得a和b互为变位词。

通过计算不在集合a和b的交集中的元素数量找到答案。

使用 a.symmetric_difference(b) 进行此类计算的计算成本是多少？ documentation

Answer 1

正如评论中所指出的，您真正需要的是多重集的一种对称差异。我们可以勾勒出这个实现的样子，看看计算成本是多少。

字符串的一个简单实现是为字符串中的符号创建两个频率 table，然后为对称差异构建第三个频率 table。

为每个输入字符串构造频率 table 很容易：

for each character in the string
    if the table contains an entry for the character
         increment the entry for the character
    otherwise
         create an entry for the character with frequency set to one

我们现在可以假设我们有两个频率 tables freq1 和 freq2。为了构造对称差异，我们可以遍历每个 table 的键并与另一个 table:

进行比较

for each character in freq1.keys
    f1 = freq1[character]
    f2 = 0
    if freq2 has an entry for character then set f2 = freq2[character]
    if f1 >= f2 then symmdiff[character] = f1 - f2

for each character in freq2.keys
    f2 = freq2[character]
    f1 = 0
    if freq1 has an entry for character then set f1 = freq1[character]
    if f2 >= f1 then symmdiff[character] = f2 - f1

我们的 table symmdiff 现在包含了足够的信息来回答您的问题：如果我们再次循环并将所有频率相加，将告诉我们必须删除的字符总数（尽管它没有具体告诉我们要从 table 中删除多少，只是合并总数；如果我们想具体了解每个 table，我们可以为每个计算两个 table差，而不是对称差）

sum = 0
for each character in symmdiff.keys
    sum = sum + symmdiff[character]

那么，这个的计算复杂度是多少？最坏的情况是每个字符串具有相同的长度并且每个字符串都由 n 个不同的字符组成（因此总共使用了 2n 个不同的字符）。那么，时间复杂度为：

两次循环遍历字符串以构建映射，每个循环的大小都与 n 成正比。
两次循环通过频率 tables 并构建大小为 2n 的频率 table。
通过大小为 2n

假设O(1) table inserts/access 并且在计算总和时忽略数字相加的真实成本，这个过程在时间和space 上基本上都是线性的。在最坏的情况下，您可以将其视为对整个输入（输入字符串对）循环三次（6n 次迭代）。

使用 python 中的对称差异从两个字符串制作 Anagrams 的计算成本

Computational cost of making Anagrams from two strings using symmetric difference in python

python

algorithm

set

computation-theory