Devise an algorithm for detecting when a string is a palindrome. Ex: A man, a plan, a canal, Panama”.
(Another from: http://www1.cs.columbia.edu/~kns10/interview/)
Example palindromes I got from a quick web search.
Don’t nod
Dogma: I am God
Never odd or even
Too bad – I hid a boot
Rats live on no evil star
No trace; not one carton
Was it Eliot’s toilet I saw?
Murder for a jar of red rum
May a moody baby doom a yam?
Go hang a salami; I’m a lasagna hog!
Satan, oscillate my metallic sonatas!
A Toyota! Race fast… safe car: a Toyota
Straw? No, too stupid a fad; I put soot on warts
Are we not drawn onward, we few, drawn onward to new era?
Doc Note: I dissent. A fast never prevents a fatness. I diet on cod
No, it never propagates if I set a gap or prevention
Anne, I vote more cars race Rome to Vienna
Sums are not set as a test on Erasmus
Kay, a red nude, peeped under a yak
Some men interpret nine memos
Campus Motto: Bottoms up, Mac
Go deliver a dare, vile dog!
Madam, in Eden I’m Adam
Oozy rat in a sanitary zoo
Ah, Satan sees Natasha
Lisa Bonet ate no basil
Do geese see God?
God saw I was dog
Dennis sinned
One reply on “Detect a palindrome”
Main thing to remember for this question is the ctype.h function toupper, isspace, and isalpha. I only used one of them here – but it will save white board space in an interview situation.
int StringPalindromeDetect(char *testStr){ int tail = 0; int head; if( testStr == (char *)NULL) return(FALSE); head = (strlen(testStr)-1); while(tail < head){ // Wind tail forward. if((testStr[tail] == ' ')||(testStr[tail] == '\'')||(testStr[tail] == ',')){ tail++; continue; } // Wind head backwards. if((testStr[head] == ' ')||(testStr[head] == '\'')||(testStr[head] == ',')){ head--; continue; } if(toupper(testStr[tail]) != toupper(testStr[head])) return(FALSE); tail++; head--; } return(TRUE); } int main(){ char *testStr = "Don't nod"; printf("\nString to test is: %s\n", testStr); if( StringPalindromeDetect( testStr ) == TRUE ){ printf("\nString is a palindrome.\n\n"); }else{ printf("\nString is not a palindrome.\n\n"); } return(0); }