检查字符串的某个回文排列是否存在

问题陈述

这里，我们给出了一个输入字符串，我们需要找出该给定字符串是否存在一个变位词是回文。如果存在，则返回 true；否则，返回 false。

什么是变位词字符串？

如果我们随机打乱一个字符串的字符顺序，那么得到的具有相同字符数的字符串就是给定字符串的变位词字符串。

例如

这里，给定的字符串 str 是 "javatpoint"

所以，对于给定的字符串可以存在各种变位词，例如 "javapointt"、"tjavapoint"、"jatavpoitn" 等。

什么是回文？

如果一个字符串从后往前读和从前往后读都是相同的，那么这个字符串就是回文字符串。

回文字符串的逆序就是字符串本身。

例如

"abcddbca"、"abcdbca" 是回文字符串的例子。

方法 1

解决这个问题的暴力方法是，我们将生成字符串的所有变位词。如果其中任何一个变位词被发现是回文，我们就返回 true；否则，我们就返回 false。

Java 代码

输出

说明

在上面的代码中，我们生成了给定字符串的所有变位词，然后检查是否有任何变位词是回文，然后将我们的答案设为 true。

我们使用一个全局布尔变量来存储结果，并将其初始值设为 false。我们调用函数 'anagram'，该函数只接受两个参数，一个是原始字符串，另一个是空字符串，它将在几个步骤后成为我们的变位词。

由于字符串的变位词只不过是其排列组合，我们使用递归方法来获取字符串的排列组合。

在每次递归调用中，我们将迭代字符串中的每个字符，将其移除并添加到我们的答案字符串中，然后对剩余的字符串调用递归函数。

对于基本情况，如果给定的字符串为空，这意味着我们已经生成了给定字符串的排列组合，并且它存储在答案字符串中。

现在我们将检查答案字符串是否是回文，然后我们将结果设为 true 并从函数返回。

要检查任何字符串的回文性，我们将使用双指针方法。我们使用左指针指向第 0 个索引，右指针指向最后一个索引。如果任何字符不匹配，我们就返回 false；否则，我们将左指针向右移动，将右指针向左移动，直到两者交叉。

复杂度

上述代码的时间复杂度为 O(!NXN)，用于生成所有排列组合，以及 O(!N*N)，用于检查字符串的回文性。所以，时间复杂度将是 **O(!NXN)**。

空间复杂度：**O(1)** 辅助空间（如果我们忽略递归调用所使用的空间）

方法 2

优化的方法非常简单。要成为回文字符串，奇数计数的字符不应超过一个。

所以我们将计算每个字符的频率，如果有一个以上字符的频率是奇数，我们就返回 true，否则返回 false。

我们可以使用频率数组或哈希映射来存储频率。

Java 代码

输出

说明

• 在上面的代码中，我们使用了字符与整数的哈希映射来存储给定字符串中存在的每个字符的频率。
• 存储了所有字符的频率后，我们将使用 keySet() 函数迭代哈希映射，并获取每个键的频率。
• 如果键的频率是奇数，我们就增加计数。
• 最后，如果计数大于一，那么可以肯定不存在回文变位词，所以我们将打印 false，否则我们将打印 true。

时间复杂度： O(N)，其中 N 是字符串中的字符数。

空间复杂度： O(K)，其中 K 是字符串中唯一字符的数量。