Valid Palindrome 解答

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.

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.

Solution

Key to the solution here is to use two pointers. Time complexity O(n), space cost O(1).

 1 public class Solution {
 2     public boolean isPalindrome(String s) {
 3         if (s == null || s.length() < 2)
 4             return true;
 5         int length = s.length();
 6         int p1 = 0, p2 = length - 1;
 7         char tmp1, tmp2;
 8         while (p1 < p2) {
 9             tmp1 = s.charAt(p1);
10             while ((!Character.isLetter(tmp1)) && (p1 < p2) && (!Character.isDigit(tmp1))) {
11                 p1++;
12                 tmp1 = s.charAt(p1);
13             }
14             if (Character.isLetter(tmp1))
15                 tmp1 = Character.toLowerCase(tmp1);
16             
17             tmp2 = s.charAt(p2);
18             while (!Character.isLetter(tmp2) && (p1 < p2) && (!Character.isDigit(tmp2))) {
19                 p2--;
20                 tmp2 = s.charAt(p2);
21             }
22             if (Character.isLetter(tmp2))
23                 tmp2 = Character.toLowerCase(tmp2);
24             if (tmp1 != tmp2)
25                 return false;
26             p1++;
27             p2--;
28         }
29         return true;
30     }
31 }