验证回文字符串

REGEX is important!

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

Input: "A man, a plan, a canal: Panama"
Output: true

我的（39 ms 😆 ）

class Solution {
	public boolean isPalindrome(String s) {
		  if (s.length()<2){
			  return true;
		  }
		  String s1 = s.replaceAll("[^a-z^A-Z^0-9]", "");
		         s1 = s1.toLowerCase();
		  System.out.println(s1);
		  char [] hui = s1.toCharArray();
		  int  n      = s1.length();
		  for(int i=0;i<(n/2);i++){
			  if (hui[i] != hui[n-i-1]){
				  return false;
			  }
		  }
		  return true;
	  }
  }

先用正则表达式把数组中非字母和数字的部分去掉，然后把大写字母转成小写字母。然后就是简单的双指针替换。当然这个算法的性能非常糟糕，不过这也引起我的哲思：因为大多数高性能算法是以牺牲简易为代价的，那么我们发明那些高度封装的函数到底是为了什么呢？

2ms

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        while(i < j){
            char c1 = validChar(s.charAt(i));
            char c2 = validChar(s.charAt(j));
            if(c1 != '\0'){
                if(c2 != '\0'){              
                    if(c1 == c2){
                        i++;
                        j--;
                    }else{
                        return false;
                    }
                }else{
                    j--;
                }
            }else{
                i++;
            }
        }
        return true;
    }

    public char validChar(char c){
        if( (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')){
            if(c >= 'A' && c <= 'Z'){
                return (char)(c + 32);
            }
            return c;
        }
        return '\0';
    }
}

4 ms

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

}

不过这也提醒我要尽可能都多掌握这些函数的用法。