Detect a palindrome

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 thought on “Detect a palindrome

  1. 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);
    }
    

Leave a Reply