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
1
2
|
Input: tactcoa
Output: True (permutations: "tacocat", "atcocta", etc.)
|
回文特征
如果给一堆字符，怎么判断它可以构成回文？回文有这么几个特征：
- <=1 个字符的计数是奇数
- >=0 个字符的计数是偶数
在这个题里的空格可以忽略的
字符计数
假设是ASCII字符集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public boolean isPalPermutation(String s) {
int oddCount = 0;
int evenCount = 0;
int[] charCount = new int[128];
for(int i = 0; i < s.length(); i++) {
int pos = s.charAt(i);
if (pos == ' ') {
continue;
}
charCount[pos]++;
if (charCount[pos] % 2 == 0) {
evenCount++;
oddCount--;
} else {
oddCount++;
if (evenCount > 0) {
evenCount--;
}
}
}
if (oddCount > 1) {
return false;
}
return true;
}
|
时间复杂度：O(n)，n=字符串长度
空间复杂度：O(c)，c=字符集大小
改进字符计数*
可以发现我们只关心奇数字符，偶数字符我们不关心，所以可以去掉偶数字符的判断：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public boolean isPalPermutation(String s) {
int oddCount = 0;
int[] charCount = new int[128];
for(int i = 0; i < s.length; i++) {
int pos = s.charAt(i);
if (pos == ' ') {
continue;
}
charCount[pos]++;
if (charCount[pos] % 2 == 0) {
oddCount--;
} else {
oddCount++;
}
}
if (oddCount > 1) {
return false;
}
return true;
}
|
评论