Problem:
Given a string, determine if a permutation of the string could form a palindrome.
For example,"code" -> False, "aab" -> True, "carerac" -> True.
General Analysis:
This problem is easy.
Basic idea is:
iff s with odd characters, only one character is allowed to appear odd times.
iff s with even characters, each character should appear even times.
Wrong Solution 1:
public class Solution {
public boolean canPermutePalindrome(String s) {
if (s == null)
throw new IllegalArgumentException("s is null");
int len = s.length();
if (len <= 1)
return true;
boolean[] odd_flag = new boolean[26];
int odd_count = 0;
for (int i = 0; i < len; i++) {
int index = s.charAt(i) - 'a';
if (odd_flag[index]) {
odd_flag[index] = false;
odd_count--;
} else{
odd_flag[index] = true;
odd_count++;
}
}
if (odd_count >= 2)
return false;
else
return true;
}
}
Mistake Analysis 1:
Runtime Error Message:
Line 12: java.lang.ArrayIndexOutOfBoundsException: -32
Last executed input:
"AaBb//a" Mistake analysis:
Lack throughly understanding of the problem, the problem does not say the character only appears in the range from 'a' to 'z'.
Wrong Solution 2:
public class Solution {
public boolean canPermutePalindrome(String s) {
if (s == null)
throw new IllegalArgumentException("s is null");
int len = s.length();
if (len <= 1)
return true;
boolean[] odd_flag = new boolean[128];
int odd_count = 0;
for (int i = 0; i < len; i++) {
int index = s.charAt(i) - '0';
if (odd_flag[index]) {
odd_flag[index] = false;
odd_count--;
} else{
odd_flag[index] = true;
odd_count++;
}
}
if (odd_count >= 2)
return false;
else
return true;
}
}
Mistake Analysis 2:
Runtime Error Message:
Line 46: java.lang.ArrayIndexOutOfBoundsException: -1
Last executed input:
"AaBb//a" Mistakes:
https://simple.wikipedia.org/wiki/ASCII
Even though the length of the ASCII table is 128, the firsrt character in the table is not '0', but null. You should not do it in such ulgy way!
Analysis 2:
Since each chracter is in the range of [0, 255], why not directly use it for indexing element???
boolean[] odd_flag = new boolean[256];
int odd_count = 0;
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (odd_flag[c]) {
..
}
}
Solution:
public class Solution {
public boolean canPermutePalindrome(String s) {
if (s == null)
throw new IllegalArgumentException("s is null");
int len = s.length();
if (len <= 1)
return true;
boolean[] odd_flag = new boolean[256];
int odd_count = 0;
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
if (odd_flag[c]) {
odd_flag[c] = false;
odd_count--;
} else{
odd_flag[c] = true;
odd_count++;
}
}
if (odd_count >= 2)
return false;
else
return true;
}
}