Friday, January 9, 2015

Valid Palindrome (LeetCode Two Pointers)

Question: 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.

Idea: First transfer the whole string to lower case. Then use two pointers i, j to scan the string. i scans from left to right, j scans from right to left. If a character is not alphanumeric, just skip it.

Time: O(n) Space: O(1)

Code with toLowerCase():
 public class Solution {  
   public boolean isPalindrome(String s) {  
     s=s.toLowerCase();  
     int i=0;  
     int j=s.length()-1;  
     while(i<j)  
     {  
       if(notAN(s.charAt(i)))  
       {  
         i++;  
         continue;  
       }  
       if(notAN(s.charAt(j)))  
       {  
         j--;  
         continue;  
       }  
       if(s.charAt(i++)!=s.charAt(j--))  
         return false;  
     }  
     return true;  
   }  
   public boolean notAN(char c)  
   {  
     if(c>='a'&&c<='z')  
       return false;  
     if(c>='0'&&c<='9')  
       return false;  
     return true;  
   }  
 }  

Code without APIs:
 public class Solution {  
   public boolean isPalindrome(String s) {  
     if(s==null||s.length()==0)  
       return true;  
     int left=0;  
     int right=s.length()-1;  
     while(left<right)  
     {  
       int codeLeft=getCode(s.charAt(left));  
       if(codeLeft==-1)  
       {  
         left++;  
         continue;  
       }  
       int codeRight=getCode(s.charAt(right));  
       if(codeRight==-1)  
       {  
         right--;  
         continue;  
       }  
       if(codeLeft!=codeRight)  
         return false;  
       left++;  
       right--;  
     }  
     return true;  
   }  
   public int getCode(char c)  
   {  
     if(c>='0'&&c<='9')  
       return (int)c;  
     if(c>='a'&&c<='z')  
       return (int)c;  
     if(c>='A'&&c<='Z')  
     {  
       return (int)(c-'A'+'a');  
     }  
     return -1;  
   }  
 }  

No comments:

Post a Comment