Leetcode 125 Valid Palindrome

雨点打透心脏的1/2处 2021-11-29 15:44 234阅读 0赞

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