Python 程序检查两个字符串是否是彼此的字谜

变位词（Anagram）是指通过重排另一个单词或短语的字母而形成的单词或短语。

例如，“listen”是“silent”的变位词，“fired”是“fried”的变位词，反之亦然。

给定两个字符串，问题是找出它们是否互为变位词。

示例 1

示例 2

方法 1 - 使用排序来检查给定的字符串是否是变位词

程序可以总结如下：

• 对两个字符串进行排序，
• 使用等于运算符 (==) 比较两个字符串
• 如果相等，则打印“Anagrams”
• 否则，打印“Not Anagrams”

输出

 
The two strings are anagrams.

说明

isAnangram 函数首先检查字符串长度是否相同。如果长度不同，则返回 false，表明字符串不可能互为变位词。如果长度相同，函数将对每个字符串中的字符进行排序和比较。如果排序后的字符串相同，则返回 True，表示原始字符串是变位词。如果排序后的字符串不相同，则原始字符串不是变位词，函数返回 False。

时间复杂度 - O(n*logn): 排序操作的时间复杂度为 O(n*logn)。

空间复杂度 - O(n): 需要额外的空间来存储排序后的字符串。

方法 2 - 使用数组存储每个字符的计数。

程序可以总结如下：

• 检查给定的字符串长度是否相同。如果不同，则返回 false。如果相同，则遵循以下步骤。
• 创建一个大小为 26 的数组，并初始化为零
• 对于字符串 one 中的每个字符，增加数组中相应索引处的字符频率
• 对于字符串 two 中的每个字符，增加数组中相应索引处的字符频率
• 在任何情况下，如果任何索引处的值变为负数，则返回 false
• 否则，返回 True

输出

 
The two strings are anagrams.

说明

isAnangram 函数首先检查字符串长度是否相同。如果长度不同，则返回 false，表明字符串不可能互为变位词。

然后，函数初始化一个大小为 26（用于 26 个英文字母）的频率数组 freq，以计算第一个字符串 str1 中每个字符的频率。使用字符的 ASCII 值，将每个字符的频率存储在 freq 数组的相应索引中。

然后，函数遍历第二个字符串 str2 中的字符，并在 freq 数组中递减每个字符的频率。如果 str2 中某个字符的频率大于 str1 中的频率，则字符串不可能是变位词，函数返回 False。

如果 str1 和 str2 中字符的频率相同，函数返回 True。

时间复杂度 - O(n): 程序遍历两个字符串的每个字符，因此其时间复杂度等于 O(n)。

空间复杂度 - O(1): 不需要额外的空间。对于所有 26 个字母，数组的大小是固定的。

方法 3 - 使用字典计算字符频率。

程序可以总结如下：

• 检查给定的字符串长度是否相同。如果不同，则返回 false。如果相同，则遵循以下步骤。
• 对于字符串 one 中的每个字符，创建一个键，并将频率作为值赋给该键。
• 对于字符串 two 中的每个字符，检查键是否存在。
• 如果键不存在或该字符的频率为零，则返回 False。
• 否则，将该键的频率减一。
• 在程序结束时，返回 True。

输出

 
The two strings are anagrams.

说明

isAnagram() 函数首先创建一个空字典来存储字符串 1 中每个字符的频率。然后，它使用 for 循环遍历字符串 one 中的每个字符，如果字符不存在，则将其作为键，然后每次将该字符的频率加一。

然后，它使用 for 循环遍历字符串 two 中的每个字符，并检查字典中是否存在该键，或者该字符的频率是否为零。如果满足任何一个条件，则返回 false。

它逐个递减每个字符的频率，并在程序结束时返回 True，表示两个字符串都是变位词。

时间复杂度 - O(n): 程序使用 for 循环遍历两个字符串

空间复杂度 - O(n): 它使用字典来存储频率。字典的大小取决于字符串的长度。

方法 4 - 使用 collections 中的 Counter()

程序可以总结如下：

• 从 collections 中导入 Counter。
• 检查给定的字符串长度是否相同。如果不同，则返回 false。如果相同，则遵循以下步骤。
• 创建两个计数器，一个用于字符串 one，一个用于字符串 two。
• 比较两个计数器。如果它们相等，则返回 True
• 否则，返回 False。

输出

 
The two strings are anagrams.

说明

Counter 类返回一个字典对象，其中每个字符作为键，频率计数作为值。isAnagram() 函数照常检查给定的字符串长度是否相同。如果字符串长度不同，则返回 False。否则，它创建两个 Counter 对象，一个用于字符串 one，另一个用于字符串 two。它比较两个计数器并返回结果。

时间复杂度 - O(n): 创建一个计数器取决于输入的大小，因此程序的 time complexity 等于 O(n)。

空间复杂度 - O(n): 程序创建了两个计数器，其大小取决于输入字符串的长度。

方法 4 - 使用 XOR 运算符

程序可以总结如下：

• 检查给定的字符串长度是否相同。如果不同，则返回 false。如果相同，则遵循以下步骤。
• 将 result 变量初始化为 0。
• 连接两个字符串。
• 遍历连接后的字符串中的字符，并与 result 执行按位 XOR。
• result = result^ord(character)
• 如果 result == 0，则返回 True，否则返回 False。

输出

 
The two strings are anagrams.

说明

当两个位不同时，XOR 运算符给出 1；当两个位相同时，XOR 运算符给出 0。

XOR 运算符的真值表

例如，如果我们对 10101 和 11011 进行 XOR，我们将得到

10101
11011
-------
01110

在 Python 中，XOR 运算符用插入符号 (^) 表示。

让我们举一个例子来理解程序的思路。

5^3 = 6
6^3 = 5
5^5 = 0

在这里，我们首先对 5 和 3 进行按位 XOR。然后是 3 和 6（上一个操作的结果）。最后，是 5 和 5（上一个操作的结果）。

上述程序也遵循同样的思路。在上述程序中，我们首先使用 + 运算符 str1 + str2 连接两个字符串。使用 for 循环，我们遍历每个字符串并与 result 执行按位 XOR。思路是，如果两个字符串是变位词，结果将为 0。否则，为某个整数。

在程序结束时，我们根据 isAnagram 函数返回的值打印结果。

时间复杂度 - O(n): 其中 n 表示 str1+str2 的大小。使用 for 循环遍历连接后的字符串。

空间复杂度 - O(1): 不需要额外的空间。