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

Question

编写一个方法来测试字符串是否满足成为回文的前提条件.

例如:

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

我在考虑这种方法:

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

我错过了什么吗？

Answer 1

您需要做的就是检查最多只有一个出现奇数的字符.这是一个Java示例:

private static boolean canMakePalindrom(String s) {
    Map<Character, Integer> countChars = new HashMap<>();

    // Count the occurrences of each character
    for (char c : s.toCharArray()) {
        Integer count = countChars.get(c);
        if (count == null) {
            count = Integer.valueOf(1);
        } else {
            count = count + 1;
        }
        countChars.put(c, count);
    }

    boolean hasOdd = false;
    for (int count : countChars.values()) {
        if (count % 2 == 1) {
            if (hasOdd) {
                // Found two chars with odd counts - return false;
                return false;
            } else {
                // Found the first char with odd count
                hasOdd = true;
            }
        }
     }

     // Haven't found more than one char with an odd count
     return true;
}

EDIT4(是的 - 这些被命令有意义,但按时间顺序编号):
上述实现具有内置的低效率.我不认为可以避免对字符串的第一次迭代,但没有真正的理由保持所有出现的计数 - 这足以跟踪具有奇数计数的那些.对于这个用例,它足以跟踪我们遇到的每个角色(例如,使用a Set),并在我们再次遇到它时将其删除.在最坏的情况下,字符串中的所有字符都不同,性能可比,但在通常情况下,每个字符出现几次,这种实现改善了第二个循环的时间和内存复杂性(这是现在减少到单一条件)戏剧性地:

private static boolean canMakePalindrom(String s) {
    Set<Character> oddChars = new HashSet<>();

    // Go over the characters
    for (char c : s.toCharArray()) {
        // Record the encountered character:
        if (!oddChars.add(c)) {
            // If the char was already encountered, remove it - 
            // this is an even time we encounter it
            oddChars.remove(c);
        }
    }

    // Check the number of characters with odd counts:
    return oddChars.size() <= 1;
}

EDIT3(是的 - 这些是有意义的,但按时间顺序编号):
Java 8提供了一个流畅的流API,可用于创建类似于下面的Python单行的实现:

private static boolean canMakePalindrom(String s) {
    return s.chars()
            .boxed()
            .collect(Collectors.groupingBy(Function.identity(),
                                           Collectors.counting()))
            .values()
            .stream()
            .filter(p -> p % 2 == 1)
            .count() <= 1;
}

编辑:
Python内置函数和理解功能使得这个太有吸引力,不发布这个单线程解决方案.它可能不如前面提到的Java效率高,但非常优雅:

from collections import Counter

def canMakePalindrom(s):
    return len([v for v in Counter(s).values() if v % 2 == 1]) <= 1

编辑2:
或者,@ DSM在评论中提出的更清晰的方法:

from collections import Counter

def canMakePalindrom(s):
    return sum(v % 2 == 1 for v in Counter(s).values()) <= 1

Answer 2

另一种方法不是计算每个字母出现的次数,而是跟踪字母是否发生了奇数或偶数次.如果一个字母发生了偶数次,你不需要担心它,只需要跟踪一组中的奇数事件.在Java中:

public static boolean canMakePalindrome(String s) {
    Set<Character> oddLetters = new HashSet<>();
    for ( char c : s.toCharArray() ) {
        if ( ! oddLetters.remove(c) ) {
            oddLetters.add(c);
        }
    }
    return oddLetters.size() <= 1;
}

Answer 3

实际上，您所要寻找的只是所有（或除一个之外的所有）字母是否配对。只要它们存在，那么它们就能够变成回文。

所以它会是这样的......

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

这不是最有效的（它会根据遇到的字母进行多次计数，即使它们已经被计数过），但它确实有效。