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

Check if a permutation of a string can become a palindrome

提问by Teepeemm

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

Eg:

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

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

例如：

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

I'm thinking of this approach:

我正在考虑这种方法：

1. Make a suffix tree for all permutation of T such that T$Reverse(T)#
2. Check for all permutation for same node

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

Am I missing anything?

我错过了什么吗？

采纳答案by Matthew

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.

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

So it would be something like...

所以它会像......

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.

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

回答by Mureinik

All you need to do is check that there's at most one character with an odd number of occurrences. Here's a Java example:

您需要做的就是检查是否最多有一个出现奇数次的字符。这是一个 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 (yes - these are ordered to make sense, but numbered by chronological order):
The above implementation has a built in inefficiency. I don't think the first iteration over the string can be avoided, but there's no real reason to keep a count of all the occurrences - it's enough to just keep track of those with the an odd count. For this usecase, it's enough to keep track of each character we encounter (e.g., with a Set), and remove it when we encounter it again. In the worst case, where all the characters in the string are different, the performance is comparable, but in the common case, where there are several occurrences of each character, this implementation improves both time and memory complexity of the second loop (which is now reduced to a single condition) dramatically:

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 (yes - these are ordered to make sense, but numbered by chronological order):
Java 8 provides a fluent streaming API which could be used to create an implementation similar to the Python one-liners below:

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

EDIT:
Python built-in functions and comprehension capabilities make this too attractive not to publish this one liner solution. It's probably less efficient than the aforementioned Java one, but is quite elegant:

编辑：
Python 内置函数和理解能力使它太有吸引力了，不能不发布这个线性解决方案。它可能不如前面提到的 Java 效率低，但非常优雅：

from collections import Counter

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

EDIT2:
Or, an even cleaner approach as proposed by @DSM in the comments:

EDIT2：
或者，@DSM 在评论中提出的更简洁的方法：

from collections import Counter

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

回答by Teepeemm

Instead of counting how many times each letter occurs, another approach keeps track of whether a letter has occurred an odd or even number of times. If a letter has occurred an even number of times, you don't need to worry about it, and only need to keep track of the odd occurrences in a set. In Java:

另一种方法不是计算每个字母出现的次数，而是跟踪字母出现的次数是奇数还是偶数。如果某个字母出现了偶数次，则无需担心，只需跟踪集合中的奇数出现次数即可。在 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;
}

回答by Lasse V. Karlsen

If I'm understanding your question correctly, this is how I understand it:

如果我正确理解你的问题，这就是我的理解：

If the input string can be rearranged into a palindrome, output "True", otherwise output "False".

如果输入字符串可以重新排列成回文，则输出“True”，否则输出“False”。

Then you can use these simple rules:

然后你可以使用这些简单的规则：

1. If the length is even, every unique character in the input has to occur a multiple of 2 times.
2. If the length is odd, every unique character except one has to occur a multiple of 2 times. Only 1 character is allowed to notoccur a multiple of 2 times.

1. 如果长度是偶数，则输入中的每个唯一字符都必须出现 2 次的倍数。
2. 如果长度为奇数，则除一个之外的每个唯一字符都必须出现 2 次的倍数。只有1个字符被允许不发生的2倍的倍数。

So for the 3 given examples:

所以对于 3 个给定的例子：

"mmo", odd length, moccurs twice (multiple of 2), ooccurs once (not a multiple of 2), so True.

“mmo”，奇数长度，m出现两次（2 的倍数），o出现一次（不是 2 的倍数），所以True.

"yakak", odd length, aoccurs twice (multiple of 2), koccurs twice (multiple of 2), yoccurs once (not a multiple of 2) , so True.

“yakak”，奇数长度，a出现两次（2 的倍数），k出现两次（2 的倍数），y出现一次（不是 2 的倍数），所以True.

"travel", more than one character does not occur a multiple of 2, so False.

“旅行”，多个字符不会出现 2 的倍数，所以False.

Additional examples:

附加示例：

"mmorpg", only moccurs a multiple of 2, the rest only once, so False.

“mmorpg”，只m出现 2 的倍数，其余只出现一次，所以False.

"mmom", no characters occur a multiple of 2, more than one character occurs "not a multiple of 2 times", so False.

“mmom”，没有字符出现 2 的倍数，多个字符出现“不是 2 的倍数”，所以False.

At this point you should realise that if only 1 character is allowed to occur a non-multiple-of-2 times, then you can disregard the length. A string with an even length will have either 2 or more characters occuring a non-multiple-of-2 times, or none at all.

此时您应该意识到，如果只允许 1 个字符出现非 2 次的倍数，那么您可以忽略长度。具有偶数长度的字符串将有 2 个或更多字符出现非 2 次的倍数，或者根本没有出现。

So the final rule should be this:

所以最终规则应该是这样的：

If at most 1 unique character occurs a non-multiple-of-2 times in the input, the output is Trueotherwise the output is False.

如果最多 1 个唯一字符在输入中出现非 2 次，则输出为 ，True否则输出为False。

回答by Jonathan Li

def can_permutation_palindrome(s):
    counter = {}
    for c in s:
        counter[c] = counter.get(c, 0) + 1
    odd_count = 0
    for count in counter.values():
        odd_count += count % 2
    return odd_count in [0, 1]

回答by user7135792

def check(string):
    bv = 0
    for s in string:
        bv ^= 1 << ord(s)
    return bv == 0 or bv & (bv - 1) == 0

回答by Mawkee

I reached the solution below today (python). I think it's readable, and performance-wise it's really good.

我今天达到了下面的解决方案（python）。我认为它是可读的，而且在性能方面它真的很好。

sum(map(lambda x: word.count(x) % 2, set(word))) <= 1

We're basically counting the number of occurrences of each character in the string "word", getting the remainder of the division by 2, summing them all and checking if you have at most 1 of them.

我们基本上是计算字符串“word”中每个字符出现的次数，将除法的余数除以 2，将它们全部相加并检查是否最多只有 1 个。

The idea is that you need to have all characters paired, except potentially for one (the middle one).

这个想法是你需要配对所有字符，除了一个（中间的）。

回答by Soudipta Dutta

Question: Can a String become a palindrome? Method1: count of characters IN Java :

问题：字符串可以变成回文吗？方法 1：Java 中的字符数：

public class TEST11 {

    public static void main(String[] args) {
        String a = "Protijayi";

        int[] count = new int[256];
        Arrays.fill(count, 0);
        for (int i = 0; i < a.length(); i++) {
            char ch = a.charAt(i);
            count[ch]++;
        } // for
            // counting of odd letters
        int odd = 0;
        for (int i = 0; i < count.length; i++) {
            if ((count[i] & 1) == 1) {
                odd++;
            }

        } // for
        if (odd > 1) {
            System.out.println("no");
        } else {
            System.out.println("yes");
        }

    }

}

IN Python:

在 Python 中：

def fix (a):
    count = [0] * 256
    for i in a: count[ord(i)] += 1
    # counting of odd characters
    odd = 0 
    for i in range(256): 
        if((count[i] & 1) == 1): odd += 1

    if(odd > 1):print("no")
    else:print("yes")


a = "Protijayi"

fix(a)

Method 2 : Use of HashSet In Java:

方法二：在Java中使用HashSet：

public class TEST11 {

    public static void main(String[] args) {

        String a = "Protijayi";
        Set<Character> set = new HashSet<>();
        for (char ch : a.toCharArray()) {

            if (set.contains(ch)) {
                set.remove(ch);
            }
            set.add(ch);
        } // for

        if (set.size() <= 1) {
            System.out.println("yes can be a palindrome");
        } else {
            System.out.println("no");
        }

    }

}

回答by Aravind Sekar

Swift example for this question.

这个问题的 Swift 示例。

var str = "mmoosl"
extension String {
func count(of needle: Character) -> Int {
    return reduce(0) {
         == needle ? 
private static boolean isStringPalindromePermutation(String input) {

    if(input == null) return false;

    if(input.isEmpty()) return false;

    int checker = 0;
    for (int i = 0; i < input.length(); i++) {
        int character = input.charAt(i) - 'a';

        int oneShiftedByNumberInCharacter = 1 << character;

        int summaryAnd = checker & oneShiftedByNumberInCharacter;
        if ( summaryAnd > 0 ) {
            int revertToShiftedByChar = ~oneShiftedByNumberInCharacter;
            checker = checker & revertToShiftedByChar;
        } else {
            checker |= oneShiftedByNumberInCharacter;
        }
    }
    if ( input.length() % 2 == 0 ) {
        if ( checker == 0) {
            return true;
        }
        else return false;
    } else {
        int checkerMinusOne = checker-1;
        if((checkerMinusOne & checker) == 0){
            return true;
        }else{
            return false;
        }
    }

}
 + 1 : ##代码##
    }
}
}



func canBeTurnedIntoAPalinpolyString(_ polyString: String) -> Bool {
var centerUsed = false
var center = Character("a")
for i in polyString {
    let count  = polyString.count(of: i)
    if count == 1 && !centerUsed {
        center = i
        centerUsed = true
    } else {
        if count % 2 != 0 {
            return false
        }
    }
}
 return true
}

print(canBeTurnedIntoAPalinpolyString(str))

回答by Vladimir Nabokov

Java

爪哇

##代码##