LeetCode 125 Valid Palindrome

思路

两个相向的指针left和right，遇到非字母和数字就直接跳过，比较left和right是否相同。
注意：
（1）left和right有范围限制；
（2）如果遇到”…” 类型的字符串，可以在比较left是否到达字符串末端来判断。

复杂度

时间复杂度O(n)
空间复杂度O(1)

代码

class Solution {
    public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) {
    return true;}int left = 0, right = s.length() - 1;while (left <= right) {
    while (left < s.length() && !isValid(s.charAt(left))) {
    left++;}// for empty string like "..."if (left == s.length()) {
    return true;}while (right >= 0 && !isValid(s.charAt(right))) {
    right--;}char lowerLeft = Character.toLowerCase(s.charAt(left));char lowerRight = Character.toLowerCase(s.charAt(right));if (lowerLeft != lowerRight) {
    return false;} else {
    left++;right--;}}return true;}private boolean isValid(char c) {
    if (('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9')) {
    return true;}return false;}
}