通过重新排列字符查找字符串中的所有回文子串

Question

为了好玩和练习，我尝试解决了以下问题（使用 C++）：Given a string, return all the palindromes that can be obtained by rearranging its characters.

我想出了一个不完全有效的算法。有时，它会找到所有回文，但有时它会找到一些但不是全部。

它的工作原理是将每对相邻的字符交换 N 次，其中 N 是输入字符串的长度。这是代码：

std::vector<std::string> palindromeGen(std::string charactersSet) {
    std::vector<std::string> pals;
    for (const auto &c : charactersSet) {
        for (auto i = 0, j = 1; i < charactersSet.length() - 1; ++i, ++j) {
            std::swap(charactersSet[i], charactersSet[j]);
            if (isPalandrome(charactersSet)) {
                if (std::find(pals.begin(), pals.end(), charactersSet) == pals.end()) {
                    // if palindrome is unique
                    pals.push_back(charactersSet);
                }
            }
        }
    }
    return pals;
}

这个算法有什么问题？我主要关心算法的功能，而不是效率。尽管我也会欣赏有关效率的提示。谢谢

Answer 1

这可能更适合代码审查，但这里是：

逻辑错误

您在迭代 charactersSet 时更改了它，这意味着您的迭代器中断了。您需要复制 characterSet，并对其进行迭代。

要改变的事情

由于 pals 仅包含唯一值，因此它应该是 std::set 而不是 std::vector。这将简化一些事情。另外，您的 isPalandrome 方法拼写回文错误！

替代方法

由于回文只能采用某种形式，考虑先对输入的字符串进行排序，这样就可以得到一个出现次数为偶数的字符列表和一个出现次数为奇数的字符列表。你只能有一个出现奇数次的字符（这只适用于奇数长度的输入）。这应该让你放弃一堆可能性。然后你可以研究一半回文的不同可能组合（因为你可以从另一半构建一半）。

Answer 2

这是另一个利用 std::next_permutation:

的实现

#include <string>
#include <algorithm>
#include <set>

std::set<std::string> palindromeGen(std::string charactersSet) 
{
    std::set<std::string> pals;
    std::sort(charactersSet.begin(), charactersSet.end());
    do
    {
        // check if the string is the same backwards as forwards
        if ( isPalindrome(charactersSet)) 
           pals.insert(charactersSet);
    } while (std::next_permutation(charactersSet.begin(), charactersSet.end()));
    return pals;
}

我们首先对原始字符串进行排序。这是 std::next_permutation 正常工作所必需的。对带有字符串排列的 isPalindrome 函数的调用是在循环中完成的。然后，如果该字符串是回文，则将其存储在集合中。随后调用 std::next_permutation 只是重新排列字符串。

这是一个Live Example。当然，它使用字符串的反向副本作为 "isPalindrome" 函数（可能效率不高），但您应该明白这一点。

通过重新排列字符查找字符串中的所有回文子串

Find All Palindrome Substrings in a String by Rearranging Characters

c++

algorithm

palindrome

逻辑错误

要改变的事情

替代方法