检查字符串的排列是否可以成为回文

Z时代
2024-01-10
分类：问答

编写一种方法来测试字符串是否满足成为回文条件的先决条件。
例如：
Input    | Output
mmo      | True  
yakak    | True  
travel   | False

我在想这种方法：

为T的所有排列制作一个后缀树，使得T $ Reverse（T）＃

检查同一节点的所有排列

我有什么想念的吗？

回答：

您真正要寻找的是是否所有（或除一个以外的）字母都配对了。只要它们是，它们就可以变成回文。

所以这就像…

bool canBeTurnedIntoAPalindrome(string drome)
{
  // If we've found a letter that has no match, the center letter.
  bool centerUsed = false;
  char center;
  char c;
  int count = 0;
  // TODO: Remove whitespace from the string.
  // Check each letter to see if there's an even number of it.
  for(int i = 0; i<drome.length(); i++)
  {
    c = drome[i];
    count = 0;
    for(int j = 0; j < drome.length(); j++)
      if (drome[j] == c)
         count++;
    // If there was an odd number of those entries
    // and the center is already used, then a palindrome
    // is impossible, so return false.
    if (count % 2 == 1)
    {
      if (centerUsed == true && center != c)
        return false;
      else
      {
        centerused = true;
        center = c;   // This is so when we encounter it again it
                      // doesn't count it as another separate center.
      }
    }
  }
  // If we made it all the way through that loop without returning false, then
  return true;
}