Palindrome Permutation
Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.
EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat", "atco cta", etc.)
DETAIL:
check if it is ANSI or Unicode
Solution
第一次遍历统计每个单词的个数
第二次遍历看看奇数个的个数是不是大于1
Complexity
时间复杂度 O(n),空间复杂度 O(n)
Code
/**
* It is also possible to finish the whole process within one pass, but as
* it is not always a optimal solution. I skip it here. What's more, bit
* vector can be used here too, but again, it is the same strategy and
* increase the opportunity of writing wrong code(bit operations are always
* easy to become a mess and hard to understand
*/
public static boolean isPalindromePermutation(String str){
String newStr = str.toLowerCase();
int[] alphabet = new int[256];
int oddCount = 0;
// 1 - pass
for (int i = 0; i < newStr.length(); i++){
if (newStr.charAt(i) != ' ') {
alphabet[newStr.charAt(i)]++;
}
}
// 2 - pass
for (int i = 0; i < alphabet.length; i++){
if (alphabet[i] != 0){
if (alphabet[i] % 2 != 0){
oddCount++;
}
}
}
if (oddCount > 1){
return false;
}
return true;
}