如何检查两个字符串是否是回文

变位词是一种文学手法。在这种手法中，如果一个词的字母是另一个词的字母重新排列而成的，那么这两个词就互称为变位词。因此，两个词的字母列表应该是相同的。例如，“abcde”和“bdeac”是互为变位词的。它们是变位词，因为两个字符串中的字母列表相同，即 ['a', 'b', 'c', 'd', 'e']。在这个问题中，我们给出了两个字符串。我们的任务是判断这两个字符串是否为变位词。让我们看一些例子来理解这个问题。

输入: s1 = "listen" s2 = "silent"

输出: 变位词

解释: 这两个词的字母列表是相同的，即 ['l', 'i', 'e', 'n', 't', 's']。

输入: s1 = "gram" s2 = "arm"

输出: 非变位词

解释: 词 "gram" 的字母列表是 ['g', 'r', 'a', 'm']，词 "arm" 的字母列表是 ['r', 'a', 'm']。由于列表不相同，因此这两个词不是变位词。

方法 - 1

在这个方法中，我们将使用一种基本的方法来解决这个问题。我们将对字符串进行排序，如果排序后的字符串相等，那么这两个字符串就是变位词。

该方法算法如下：

• 我们将对给定的两个字符串进行排序
• 然后，我们将比较排序后的字符串。
• 如果排序后的字符串相等，我们将返回 True
• 否则，我们将返回 False

下面是该方法在 Python 中的实现。

代码

输出

The given two strings are not anagrams

时间复杂度: 此方法的时间复杂度是对数级的。执行排序的时间复杂度为 O(log N)。

空间复杂度: 我们没有使用任何额外的空间，因此空间复杂度为 O(1)。

方法 - 2

在这个方法中，我们将通过计算字母的频率来检查字符串是否为变位词。

我们将计算两个字符串中每个字符的频率，如果字符串包含相同的字符并且每个字符的频率都匹配，那么给定的字符串就是变位词。

让我们看看该方法的算法：

• 我们将初始化两个长度等于字符串可能包含的总字符数的数组，即 256。我们将所有数组元素的值初始化为 0。
• 我们将逐个迭代两个字符串，并更新相应数组中字符的频率。
• 然后，我们将比较计数数组。我们将比较两个字符串的字符计数频率，如果所有频率都相同，则字符串是变位词，如果任何一个字符的频率不同，则字符串不是变位词。

下面是上述方法的实现。

代码

时间复杂度: 此方法的时间复杂度是对数级的。执行排序的时间复杂度为 O(log N)。

空间复杂度: 我们没有使用任何额外的空间，因此空间复杂度为 O(1)。

方法 - 2

在这个方法中，我们将通过计算字母的频率来检查字符串是否为变位词。

我们将计算两个字符串中每个字符的频率，如果字符串包含相同的字符并且每个字符的频率都匹配，那么给定的字符串就是变位词。

让我们看看该方法的算法：

• 我们将初始化两个长度等于字符串可能包含的总字符数的数组，即 256。我们将所有数组元素的值初始化为 0。
• 我们将逐个迭代两个字符串，并更新相应数组中字符的频率。
• 然后，我们将比较计数数组。我们将比较两个字符串的字符计数频率，如果所有频率都相同，则字符串是变位词，如果任何一个字符的频率不同，则字符串不是变位词。

下面是上述方法的实现。

代码

输出

The given two strings are not anagrams

时间复杂度: 我们使用线性循环来解决这个问题，因此时间复杂度为 O(n)。

辅助空间: 我们创建了两个数组来存储字母的频率，因此空间复杂度为 O(N)，其中 N 是字符总数，即 256。

方法 - 3

在这个方法中，我们将使用 HashSet 来检查给定的两个字符串是否互为变位词。

这种方法是上述方法的优化解决方案。我们不需要创建长度为 256 的计数数组。我们可以使用哈希集来存储每个字符的频率。

在这个方法中，我们不会创建两个哈希集，而是只使用一个哈希集。我们将存储一个字符串的字符频率。然后，我们将迭代另一个字符串并减少字符的频率。如果最后所有字符的频率都为零，则给定的字符串互为变位词。如果不是这样，则字符串不是变位词。

该方法算法如下：

• 我们将创建一个哈希集。
• 然后，我们将迭代其中一个字符串并将频率存储在哈希集中。
• 然后，我们将迭代另一个字符串并进行检查
• 如果字符存在于哈希集中，则减少频率
• 否则，返回 false，因为字符集不匹配。
• 最后，我们将检查每个键的频率是否为零。
  • 如果不为零，则返回 False。
• 最后，返回 True。

下面是上述方法的实现。

代码

输出

The given two strings are not anagrams

时间复杂度: 该方法的时间复杂度为线性，因为我们使用了线性循环来解决问题。因此，时间复杂度为 O(N)。

空间复杂度: 此程序的空间复杂度比前一个程序低。在此方法中，我们只创建了一个长度为 N 的哈希集。因此，空间复杂度为 O(N)。