力扣 5. 最长回文子串 & 125. 验证回文串

5题目描述：

给你一个字符串s，找到s中最长的回文子串。

解析：

1.如果字符串长度小于2，直接返回原字符串
2.定义两个变量，一个start存储当前找到的最大回文字符串的起始位置，
另一个maxLength记录字符串的长度（终止位置就是start+maxLength）
3.创建一个helper function，判断左边和右边是否越界，同时最左边的字符是否等于最右边的字符。
如果以上三个条件都满足，则判断是否需要更新回文字符串最大长度及最大字符串的起始位置，
然后将left--，right++，继续判断，知道不满足三个条件之一。
4.遍历字符串，每个位置调用helper function两遍
第一遍检查i-1和i+1
第二遍检查i和i+1

Java:

private int start = 0, maxLength = 1;
    public String longestPalindrome(String s) {
        if(s.length() < 2) {
            return s;
        }
        for(int i = 0; i < s.length(); i++) {
            expandAroundCenter(s, i-1, i+1);
            expandAroundCenter(s, i, i+1);
        }
        return s.substring(start, start + maxLength);
    }
    private void expandAroundCenter(String s, int left, int right) {
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            if(right - left + 1 > maxLength) {
                maxLength = right - left + 1;
                start = left;
            }
            left--;
            right++;
        }
    }

JavaScript:

var longestPalindrome = function(s) {
    if(s.length < 2) {
        return s;
    }
    let start = 0;
    let maxLength = 1;
    function expandAroundCenter(left, right) {
        while(left >= 0 && right < s.length && s[left] === s[right]) {
            if(right - left + 1 > maxLength) {
                maxLength = right - left + 1;
                start = left;
            }
            left--;
            right++;
        }
    }
    for(let i = 0; i < s.length; i++) {
        expandAroundCenter(i-1, i+1);
        expandAroundCenter(i,i+1);
    }
    return s.substring(start, start + maxLength);
};

125题目描述：

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

解析：

双指针

Java：

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

JavaScript:

var isPalindrome = function(s) {
    s = s.toLowerCase().replace(/[\W_]/g, "");
    if(s.length < 2) {
        return true;
    }
    let left = 0;
    let right = s.length - 1;
    while(left < right) {
        if(s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
};