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

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. 检查相同节点的所有排列

我有什么遗漏的吗？

- user5080124

---

你只需要对所有字符进行排列组合，并检查每个结果序列是否与其本身的反转相等。 - Adam Arold

你的意思是：这个字符串是否存在一个排列是回文的？ 不幸的是，标题和问题都有错误。 - Ami Tavory

测试结果表明你不需要进行任何排列组合，只需要进行一些审核：如果字符串长度为奇数，则应该有一个且仅有一个字符在整个字符串中出现的总次数为奇数；如果字符串长度为偶数，则所有字符在整个字符串中出现的总次数都应该是偶数。如果符合这些条件，那么你实际上正在使这个问题变得更加复杂。 - Jason Hu

所以基本上你想确定是否可以将输入字符串的字符重新排列成回文？如果是这样，那么答案是“是”，如果 1）长度为偶数，并且每个唯一字符出现了偶数次，或者 2）长度为奇数，并且每个唯一字符出现了偶数次，除了一个。 - Lasse V. Karlsen

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

编辑3（是的-这些被排序以使其有意义，但按时间顺序编号）：
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

- Mureinik

---

“aa”怎么办？你的解决方案没有检测到它是回文吗？ - MAA

@MAA 为什么你认为这些解决方案都无法检测到 "aa"？我已经对 "aa" 运行了所有五个解决方案，它们都返回 true。 - Mureinik

你说得对。我一开始以为没有任何字符出现了奇数次，但这不是问题。 - MAA

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

- Teepeemm

Answer 3

如果我正确理解了您的问题，那么我对其的理解如下：

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

然后您可以使用以下简单规则：

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

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

"mmo"，长度为奇数，'m'出现两次(2的倍数)，'o'出现一次(不是2的倍数)，所以输出"True"。

"yakak"，长度为奇数，'a'出现两次(2的倍数)，'k'出现两次(2的倍数)，'y'出现一次(不是2的倍数)，所以输出"True"。

"travel"，有不止一个字符没有出现2的倍数次，所以输出"False"。

其他例子：

"mmorpg"，只有'm'出现了2的倍数次，其他只出现了一次，所以输出"False"。

"mmom"，没有字符出现2的倍数次，有超过一个字符出现了“不是2的倍数次”，所以输出"False"。

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

因此最终规则应该是：

如果输入中最多一个唯一字符出现非2的倍数次，则输出“True”，否则输出“False”。

- Lasse V. Karlsen

Answer 4

您所需要的就是检查所有字母是否成对出现（或只有一个未成对）。只要它们成对出现，那么它们就可以变成回文。

因此，这将类似于...

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

这不是最有效的方法（它会多次计算相同字母的数量，即使已经计算过），但它可以正常工作。

- Matthew

Answer 5

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]

- Jonathan Li

---

虽然这段代码片段可能解决了问题，但包括解释真的有助于提高您的帖子质量。请记住，您正在为未来的读者回答问题，而这些人可能不知道您的代码建议原因。请尽量不要在代码中添加过多的解释性注释，这会降低代码和解释的可读性！ - Box Box Box Box

Python的方法可以从使用collections.Counter中受益，这基本上就是这样。 - Teepeemm

Answer 6

我今天想到了以下的解决方案（使用Python）。我认为它很易读，并且在性能方面表现非常好。

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

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

这个想法是你需要所有字符成对出现，除了可能有一个（中间的字符）。

- Mawkee

Answer 7

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

- user7135792

Answer 8

具有O(n)复杂度。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PallindromePemutation
{
    class charcount
    {
        public char character { get; set; }
        public int occurences { get; set; }
    }
    class Program
    {
        static void Main(string[] args)
        {

            List<charcount> list = new List<charcount>();
            charcount ch;
            int count = 0;
            char[] arr = "travel".ToCharArray();
            for (int i = 0; i < arr.Length; i++)
            {
                charcount res = list.Find(x => x.character == arr.ElementAt(i));
                if (res == null)
                {
                    ch = new charcount();
                    ch.character = arr.ElementAt(i);
                    ch.occurences = 1;
                    list.Add(ch);
                }
                else
                {
                    charcount temp=  list.Find(x => x.character == arr.ElementAt(i));
                    temp.occurences++;
                }
            }
            foreach (var item in list)
            {
                if (!(item.occurences % 2 == 0))
                {
                    count++;
                }
            }
            if (count > 1)
            {
                Console.WriteLine("false");
            }
            else
            {
                Console.WriteLine("true");
            }
            Console.ReadKey();
        }
    }
}

- hussain

Answer 9

问题：一个字符串能否变成回文？ 方法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");
        }

    }

}

在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)

方法二：使用 HashSet 在 Java 中：

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

    }

}

- Soudipta Dutta

Answer 10

我的想法是，如果有奇数计数的字母数量为1，其余都是偶数计数，那么就可能是回文。这是我用Python编写的程序

string = raw_input()

found = False
char_set = set(string) # Lets find unique letters

d_dict = {}
for c in char_set:
    d_dict[c] = string.count(c) # Keep count of each letter

odd_l = [e for e in d_dict.values() if e%2 == 1] # Check how many has odd number of occurrence     
if len(odd_l) >1:
    pass
else:
    found = True



if not found:
    print("NO")
else:
    print("YES")

- Arindam Roychowdhury