Pregunta de entrevista de Google
Given a string, return true if after jumbling/rearranging the characters of the string will it be a palindrome. and false if not.
eg: given string "evlel", it can be rearranged to "level" and thus it is a palindrome, and return true.
eg: 1234 cannot be rearranged to become a palindrome hence false.
Respuestas de entrevistas
A palindrome is a word that has the same spelling forward and backwards. “1234” are numbers and cannot be a palindrome.
“acrecar” is a palindrome by that definition of the word, “racecar”, “dad”, “pop”, “poop”. These I feel like may be better examples. “454” would be an example of a palindrome that is a number.
Count the occurrence of each character; if more than one char has odd number of occurrences, it’s false
This solution uses an unordered map to be O(n)
#include
#include
#include
int main()
{
std::unordered_map map;
const std::string test = "aabbbaaccc";
for(size_t i = 0; i ::const_iterator it = map.begin(); it != map.end(); ++it)
{
if (it->second % 2 != 0)
{
oddNumber++;
if (oddNumber > 1)
{
std::cout << "Not palindrome" << std::endl;
return -1;
}
}
}
std::cout << "Palindrome" << std::endl;
return 0;
}