Categories
Uncategorized

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

Leave a Reply