125.Valid Palindrome

题目大意：给出一个字符串，判断去除特殊字符和空格后的字符串（只包括字母和数字）是否是回文串。

法一：用辅助数组记录去除了特殊字符和空格后的字符串，然后针对这个辅助数组判断是否是回文串。o(n)。代码如下（耗时9ms）：

 1 public boolean isPalindrome(String s) {
 2         boolean res = true;
 3         int len = s.length(), k = 0;
 4         char[] tmp = new char[len];
 5         //去除空格和特殊字符，将所有字母转小写
 6         for(int i = 0; i < len; i++) {
 7             if((s.charAt(i) >= 'a' && s.charAt(i) <= 'z' ) || (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
 8                 tmp[k++] = s.charAt(i);
 9             }
10             //大写转小写
11             else if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
12                 tmp[k++] = (char)(s.charAt(i) + 32);
13             }
14         }
15         //判断是否是回文
16         int left = 0, right = k - 1;
17         while(left <= right) {
18             if(tmp[left] == tmp[right]) {
19                 left++;
20                 right--;
21                 continue;
22             }
23             else {
24                 res = false;
25                 break;
26             }
27         }
28         return res;
29     }

View Code

法二：直接跳过特殊字符和空格，利用Character的封装方法判断是否是字母和数字，如果是字母和数字，则判断是否相等。代码如下（耗时9ms）：

 1     public boolean isPalindrome(String s) {
 2         boolean res = true;
 3         int left = 0, right = s.length() - 1;
 4         while(left <= right) {
 5             //左边非数字和字母
 6             if(!Character.isLetterOrDigit(s.charAt(left))) {
 7                 left++;
 8             }
 9             //右边非数字和字母
10             else if(!Character.isLetterOrDigit(s.charAt(right))) {
11                 right--;
12             }
13             //如果都是数字和字母
14             else {
15                 //判断是否回文相等
16                 if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
17                     res = false;
18                     break;
19                 }
20                 left++;
21                 right--;
22             }
23         }
24         return res;
25     }

View Code