leetcode16 Valid Palindrome

超、凢脫俗 2021-12-14 04:49 145阅读 0赞

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
    
    Note: For the purpose of this problem, we define empty string as valid palindrome.
    
    Example 1:
    
    Input: "A man, a plan, a canal: Panama"
    Output: true
    Example 2:
    
    Input: "race a car"
    Output: false

给定一个字符串，确定它是否是回文，只考虑字母数字字符并忽略大小写。  
注意：出于此问题的目的，我们将空字符串定义为有效的回文。

思路：

1.  先判断字符串是否为空，如果为空则直接返回true.
2.  字符串转为小写字母或者大写字母，
3.  然后依次循环字符串，将字符和数字的全部放到新的字符串中
4.  最后一个新字符串反转，然后与原字符串做对比。
5.  如果相等，则返回true,否则返回false。

我的代码实现：

class Solution {
        public boolean isPalindrome(String s) {
             if (s == null || s.length() == 0){
                return  true;
            }
            String str = s.toLowerCase();
            StringBuilder pre = new StringBuilder();
            StringBuilder aft = new StringBuilder();
            for (int i=0;i<str.length();i++){
                char c = str.charAt(i);
             
                if((c >= 'a' && c <= 'z') || Character.isDigit(c)){
                     pre.append(str.charAt(i));
                    aft.append(str.charAt(i));
                }
            }
            return pre.reverse().toString().equals(aft.toString());
        }
    }

Runtime: 8 ms, faster than 37.28% of Java online submissions for Valid Palindrome.
    Memory Usage: 39.4 MB, less than 15.40% of Java online submissions for Valid Palindrome.

discuss中的几种好的解法：

class Solution {
       private static final char[]charMap = new char[256];
    	static{
    	    for(int i=0;i<10;i++){
    	        charMap[i+'0'] = (char)(1+i);  // numeric
    	    }
    	    for(int i=0;i<26;i++){
    	        charMap[i+'a'] = charMap[i+'A'] = (char)(11+i);  //alphabetic, ignore cases
    	    }
    	}
    	public boolean isPalindrome(String s) {
    	    char[]pChars = s.toCharArray();
    	    int start = 0,end=pChars.length-1;
    	    char cS,cE;
    	    while(start<end){
    	        cS = charMap[pChars[start]];
    	        cE = charMap[pChars[end]];
    	        if(cS!=0 && cE!=0){
    	            if(cS!=cE)return false;
    	            start++;
    	            end--;
    	        }else{
    	            if(cS==0)start++;
    	            if(cE==0)end--;
    	        }
    	    }
    	    return true;
    	}
    }

Runtime: 1 ms, faster than 100.00% of Java online submissions for Valid Palindrome.
    Memory Usage: 37.8 MB, less than 57.29% of Java online submissions for Valid Palindrome.

下面这个思路是：首先了解一下回文，最后一个和第一个是同一个数字或者字母，所以在这道题中我们只需要关注字母和数字就可以。

1.  开始循环，start被设为0，end被设为字符串的长度-1
2.  当`start<end`的时候，且开始的字符不是字母或者数字的时候，start加1
3.  当`start<end`的时候，且结束的字符不是字母或者数字的时候，end减1
4.  如果从前开始和从后开始的字母或者数字转为小写不相等返回false,否则返回true。

class Solution {
      public boolean isPalindrome(String s) {
            int start = 0; 
            int end = s.length() - 1;
            while(start <= end) {
                while(start <= end && !Character.isLetterOrDigit(s.charAt(start))) {
                    start++;
                }
                while(start <= end && !Character.isLetterOrDigit(s.charAt(end))) {
                    end--;
                }
                if(start <= end && Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))) {
                    return false;
                }
                start++;
                end--;
            }
            return true;
        }
    }

Runtime: 4 ms, faster than 83.87% of Java online submissions for Valid Palindrome.
    Memory Usage: 39.1 MB, less than 23.71% of Java online submissions for Valid Palindrome.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20211213/8dda46e5525f4be0b8c42bf4fef5e9db.png