Leetcode 125 Valid Palindrome

lc125 Valid Palindrome

法一:

双指针

首尾指针向中间收缩,比较两者指向元素是否相同

不相同就返回false

若遇到非数字非字母的字符,跳过,这里可以手写if判断,也可以用Character内置函数Character.isLetterOrDigit()

还有一点需要注意,同一个字母的小写形式和大写形式应当被判定为相同,但是==比较时,两者的ascii值不同,可以手写if判断,也可以用Character.toLowerCase(),统一成小写或大写形式,

注意while终止条件 i<j即可

奇数个字母时,两个指针最终会相同,但是我们不需要比较他们,因为这对回文串没有任何影响;

偶数个字母时,两个指针刚好差1,i<j可以覆盖这种情况

 1 class Solution {
 2     public boolean isPalindrome(String s) {
 3         for(int left = 0, right = s.length()-1; left < right;){
 4             if(!Character.isLetterOrDigit(s.charAt(left)))
 5                 left++;
 6             else if(!Character.isLetterOrDigit(s.charAt(right)))
 7                 right--;
 8             else{
 9                 if(Character.toLowerCase(s.charAt(left++)) != Character.toLowerCase(s.charAt(right--)))
10                     return false;
11             }
12         }
13         return true;
14     }
15 }

法二:

将数字和字母从ascii值映射到1-10,11~36(大小写映射到同一个值所以只有26而非52),其它字符统统算为0

这样可以大大缩短调用isLetterOrDigit和toLowerCase的时间

 1 class Solution {
 2     public static final int[] charmap = new int[128];
 3     static{
 4         for(int i=0; i<10; i++)
 5             charmap[i + '0'] = i+1;
 6         for(int i=0; i<26; i++)
 7             charmap[i + 'a'] = charmap[i + 'A'] = i+11;
 8     }
 9     public boolean isPalindrome(String s) {
10         for(int left = 0, right = s.length() - 1; left < right; ){
11             if(charmap[s.charAt(left)] == 0)
12                 left++;
13             else if(charmap[s.charAt(right)] == 0)
14                 right--;
15             else{
16                 if(charmap[s.charAt(left++)] != charmap[s.charAt(right--)])
17                     return false;
18             }
19         }
20         return true;
21     }
22 }
原文地址:https://www.cnblogs.com/hwd9654/p/11022808.html