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

Question

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

8

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

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

我在考虑这个方法：

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

我有什么遗漏的吗？

- user5080124

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

3

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

3

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

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

24个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mahesh · Answer 1

更高效的实现 - Java

boolean palindromeRearranging(String inputString) {
    Map<Character, Integer> charsCount = new HashMap<Character, Integer>();
    for(char c : inputString.toCharArray()){
        charsCount.compute(c, (key, val) ->  val == null ? 1 : val + 1);
    }
    List<Integer> result = new ArrayList<>();
    charsCount.forEach((k, v) -> {
        if(v % 2 != 0){
            result.add(v);
        }
    });
    return (result.size() == 0 || result.size() == 1);
}

- Aravind Sekar · Answer 2

这个问题的Swift示例。

var str = "mmoosl"
extension String {
func count(of needle: Character) -> Int {
    return reduce(0) {
        $1 == needle ? $0 + 1 : $0
    }
}
}



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

- Vladimir Nabokov · Answer 3

Java

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

}

- Jesus Dana · Answer 4

从检查字符串是否为回文排列实现

时间复杂度本质上是O(n)。这意味着该函数在输入字符串的长度上是线性的。

public static boolean isPermutationOfPalindrome(String str) {
    // Convert the input string to lower case and remove any non-letter characters
    str = str.toLowerCase().replaceAll("[^a-z]", "");

    // Create an array to count the frequency of each letter
    int[] charCounts = new int[26];
    for (int i = 0; i < str.length(); i++) {
        charCounts[str.charAt(i) - 'a']++;
    }

    // Check if there is at most one character with an odd frequency
    boolean foundOdd = false;
    for (int count : charCounts) {
        if (count % 2 == 1) {
            if (foundOdd) {
                return false;
            }
            foundOdd = true;
        }
    }
    return true;
}