Apple
Microsoft
2020-05-24
266. Palindrome Permutation
Similar Question: LeetCode Question 1457
Question:
Given a string, determine if a permutation of the string could form a palindrome.
Example 1:
Input: "code"
Output: false
Example 2:
Input: "aab"
Output: true
Example 3:
Input: "carerac"
Output: true
Solution:
Using hash table to record the frequency of each character, if there are more than one character have the odd frequency, return false. Otherwise, it has a permutation which can form a palindrome.
class Solution {
public boolean canPermutePalindrome(String s) {
if (s == null || s.length() == 0) return false;
int[] hash = new int[128];
int counter = 0;
for(char c: s.toCharArray()) {
hash[c]++;
}
for (int i : hash) {
if (i % 2 == 1) {
counter++;
}
if (counter > 1) {
return false;
}
}
return true;
}
}