检查字符串的排列是否可以变成回文 [英] Check if a permutation of a string can become a palindrome

问题描述

编写一种方法来测试字符串是否满足成为回文的先决条件.

Write a method to test if a string meets the preconditions to become a palindrome.

例如:

Input    | Output
mmo      | True  
yakak    | True  
travel   | False

我正在考虑这种方法:

1. 为T的所有排列制作一个后缀树，使得T $ Reverse(T)#
2. 检查同一节点的所有排列

我想念什么吗?

推荐答案

您真正要查找的是是否所有字母(或除一个以外的所有字母)都已配对.只要它们是，它们就可以变成回文.

Really all you're looking for is if all (or all but one) of the letters are paired off. As long as they are, then they will be able to be turned into a palindrome.

所以它就像...

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;
}

这不是最有效的方法(即使已经算过字母，它也会对字母进行多次计数)，但是它确实有效.

This isn't the most efficient (it's counting letters as many times as it comes across them, even if they've been counted already) but it does work.

这篇关于检查字符串的排列是否可以变成回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！