Palindrome Permutation
1.4 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
Input: Tact Coa
Output: True (permutations:"taco cat'; "atco cta'; etc.)
- My first method involve using a hash table. While this algorithm will preform in O(N) time, we use a long of additional extra space.
- I first store the elements into a hash table, along with their frequencies, making sure to ignore spaces, and invalid characters.
- Next, I iterate through this hash table to check for valid frequencies. Even lengthed strings must have a frequencies of even elements, and odd length strings must have 1 single frequency char with the remainder of the characters having a even number of frequencies.
bool isPalindromic(string str) {
if (str.length() < 2) return true;
str.erase(remove_if(str.begin(), str.end(), isspace), str.end());
transform(str.begin(), str.end(), str.begin(), ::tolower);
unordered_map <char, int> char_frequency;
for (auto i : str) {
if (!isalpha(i)) continue;
auto &found = char_frequency.find(i);
if (found == char_frequency.end()) {
// not found
char_frequency.insert({ i, 1 });
}
else {
// found
found->second++;
}
}
// count duplicates
if (str.length() % 2 == 0) {
// even
for (auto i : char_frequency) {
if (i.second != 2) {
return false;
}
}
return true;
}
else {
// odd
bool one_odd_flag = false;
for (auto i : char_frequency) {
if (i.second == 1 && !one_odd_flag) {
one_odd_flag = true;
}
else if (i.second != 2 && one_odd_flag) {
return false;
}
}
return one_odd_flag;
}
}
int main() {
cout << boolalpha << isPalindromic("Tact Coa") << endl;
cout << boolalpha << isPalindromic("asijdia") << endl;
cout << boolalpha << isPalindromic("aassdd") << endl;
cout << boolalpha << isPalindromic("asdasde") << endl;
cout << boolalpha << isPalindromic("sdd") << endl;
pause();
}
- The second approach is more attractive in my opinion, although it is a little less elegent. The approach is to first sort a valid string, and then compare the elements in place to confirm whether the next element is a duplicate. I've applied the same idea for when an element is odd, we allow for one free be.
- O(nlogn) time, O(1) space
bool isPalindromic(string str) {
if (str.length() < 2) return true;
str.erase(remove_if(str.begin(), str.end(), isspace), str.end());
transform(str.begin(), str.end(), str.begin(), ::tolower);
unordered_map <char, int> char_frequency;
for (auto i : str) {
if (!isalpha(i)) continue;
auto &found = char_frequency.find(i);
if (found == char_frequency.end()) {
// not found
char_frequency.insert({ i, 1 });
}
else {
// found
found->second++;
}
}
// count duplicates
if (str.length() % 2 == 0) {
// even
for (auto i : char_frequency) {
if (i.second % 2 != 0) {
return false;
}
}
return true;
}
else {
// odd
bool one_odd_flag = false;
for (auto i : char_frequency) {
if (i.second % 2 != 0 && !one_odd_flag) {
one_odd_flag = true;
}
else if (i.second % 2 != 0 && one_odd_flag) {
return false;
}
}
return one_odd_flag;
}
}
Last modified 4yr ago