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

第二次做法：用API

 1 public class Solution {
 2     public boolean isPalindrome(String s) {
 3         if (s == null) return false;
 4         if (s.length() == 0) return true;
 5         int l=0, r=s.length()-1;
 6         while (l < r) {
 7             while (l<r && !Character.isLetterOrDigit(s.charAt(l))) l++;
 8             while (l<r && !Character.isLetterOrDigit(s.charAt(r))) r--;
 9             if (l == r) break;
10             if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;
11             else {
12                 l++;
13                 r--;
14             }
15         }
16         return true;
17     }
18 }

第一次做法：难度：79. 这道题是判断一个字符串是不是回文串。因为只是看一个字符串，算法还是比较简单，就是从两头出发，往中间走，进行两两匹配。这里面的小问题就是在这个题目要求中，只判断字母和数字类型的字符，其他字符直接跳过即可。因此我们要写一个函数判断他是不是合法字符，而且因为忽略大小写，我们在判断两个字符是不是相同的时候如果是大写，要转成相应的小写字母。这个算法从两边扫描，到中间相遇，只需要一次线性扫描，复杂度是O(n)，空间上是O(1)。

 1 public class Solution {
 2     public boolean isPalindrome(String s) {
 3         if (s == null) return false;
 4         if (s.length() == 0) return true;
 5         int l=0, r=s.length()-1;
 6         while (l < r) {
 7             while (l<r && !isAlpha(s, l)) l++;
 8             while (l<r && !isAlpha(s, r)) r--;
 9             if (l == r) break;
10             if (!isSame(s, l, r)) return false;
11             else {
12                 l++;
13                 r--;
14             }
15         }
16         return true;
17     }
18     
19     public boolean isAlpha(String s, int i) {
20         char c = s.charAt(i);
21         if (c>='A'&&c<='Z' || c>='a'&&c<='z' || c>='0'&&c<='9') return true;
22         return false;
23     }
24     
25     public boolean isSame(String s, int l, int r) {
26         char left = s.charAt(l);
27         char right = s.charAt(r);
28         if (left>='A' && left<='Z') left = (char)(left-'A'+'a');
29         if (right>='A' && right<='Z') right = (char)(right-'A'+'a');
30         return left==right;
31     }
32 }

28行和29行如果不强制转换类型，会出现possible loss of precision的错误