Palindrome Permutation
Total Accepted: 11227 Total Submissions: 22276 Difficulty: Easy
Given a string, determine if a permutation of the string could form a palindrome.
For example,
"code" -> False, "aab" -> True, "carerac" -> True.
思路
- Sort: Time: O(nlogn) Space 0(1)
- HashSet: Time: O(n) Spcace O(n)
Sort
public class Solution {
public boolean canPermutePalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}
int size = s.length();
char[] array = s.toCharArray();
Arrays.sort(array);
if (size % 2 == 0) {
for (int i = 0; i + 1< size; i = i + 2) {
if (array[i] != array[i + 1]) {
return false;
}
}
} else {
boolean singleCharAlready = false;
for (int i = 0; i + 1 < size;) {
if (array[i] != array[i + 1]) {
if (singleCharAlready) {
return false;
}
singleCharAlready = true;
i++;
continue;
}
i = i + 2;
}
}
return true;
}
}
HashSet
public class Solution {
public boolean canPermutePalindrome(String s) {
Set<Character> set=new HashSet<Character>();
for(int i=0; i<s.length(); ++i){
if (!set.contains(s.charAt(i)))
set.add(s.charAt(i));
else
set.remove(s.charAt(i));
}
return set.size()==0 || set.size()==1;
}
}