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
代码
Approach #1 Brute Force
If a string with an even length is a palindrome, every character in the string must always occur an even number of times. If the string with an odd length is a palindrome, every character except one of the characters must always occur an even number of times. Thus, in case of a palindrome, the number of characters with odd number of occurences can't exceed 1(1 in case of odd length and 0 in case of even length).
class Solution {
public boolean canPermutePalindrome(String s) {
int count = 0;
for (char i = 0; i < 128 && count <= 1; i++) {
int ct = 0;
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == i) {
ct++;
}
}
count += ct % 2;
}
return count <= 1;
}
}
Approach #2 Using HashMap
class Solution {
public boolean canPermutePalindrome(String s) {
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
}
int count = 0;
for (char key: map.keySet()) {
count += map.get(key) % 2;
}
return count <= 1;
}
}
Approach #3 Using Array
class Solution {
public boolean canPermutePalindrome(String s) {
int[] map = new int[128];
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i)]++;
}
int count = 0;
for (int key = 0; key < map.length && count <= 1; k++) {
cont += map[key] % 2;
}
return count <= 1;
}
}
Approach #4 Single Pass
class Solution {
public boolean canPermutePalindrome(String s) {
int[] map = new int[128];
int count = 0;
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i)]++;
if (map[s.charAt(i)] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
}
Approach #5 Using Set
class Solution {
public boolean canPermutePalindrome(String s) {
Set<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if (!set.add(s.charAt(i))) {
set.remove(s.charAt(i));
}
}
return set.size() <= 1;
}
}