Tuesday, May 16, 2017

Valid Palindrome


Problem Statement

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Example:


"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Link to GitHub Java  :Code
Link to GitHub JavaScript:  Code



Solution

  • We need 2 pointers head and tail
  • Head is the initial position and tail is the last position in the array
  • Increment the header if we do not find valid character .Decrement the tail if we do not find the valid character.
  • Loop through the array till we find tail is greater than head
  • Return false if header character is not equal to tail
public static boolean get(String str)
 {
  //if string is empty return true
  if(str.isEmpty())
  {
   return true;
  }
  int head =0, tail=str.length()-1;
  //loop  through the strings to find if it is a valid palindrome
   while(head <= tail)
   {
    //Increment the header if the character isLetter or digit
    if(!Character.isLetterOrDigit(str.charAt(head))){
     head++;
    }
    //Decrement the tail if the character isLetter or digit
    else if(!Character.isLetterOrDigit(str.charAt(tail))){
     tail--;
    }
    else {
       if(Character.toLowerCase(str.charAt(head)) 
                                     !=Character.toLowerCase(str.charAt(tail)))
       {
        return false;
       }
       head++;
       tail--;
     
    }
   }
  return true;
 }

No comments:

Post a Comment