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

Question

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

Eg:

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(是的 - 这些是为了有意义而排列的，但按时间顺序编号):
上面的实现有一个内置的低效率。我不认为可以避免对字符串的第一次迭代，但是没有真正的理由去计算所有出现的次数——只跟踪那些出现奇数的次数就足够了。对于这个用例，跟踪我们遇到的每个字符就足够了(例如，使用 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