Labels

Wednesday, March 4, 2015

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For 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.

Naive Way: Keep two pointers starting from both beginning and end, check equality of two valid characters.

 public class Solution {  
   public boolean isPalindrome(String s) {  
     s = s.toLowerCase();  
     int begin = 0, end = s.length()-1;  
     while(begin < end){  
       while(!isAlphanumeric(s.charAt(begin)) && begin < end) begin++;  
       while(!isAlphanumeric(s.charAt(end)) && begin < end) end--;  
       if(s.charAt(begin)!= s.charAt(end)) return false;  
       begin++;  
       end--;  
     }  
     return true;  
   }  
   public boolean isAlphanumeric(char c){  
     return c >= '0' && c <='9' || c >= 'a' && c <= 'z';  
   }  
 }  


No comments:

Post a Comment