Longest Palindromic Substring

题目地址：
https://leetcode.com/problems/longest-palindromic-substring/#/description

题目：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of sis 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

解题思路：just use as current index as extend to the left and right. keep lo and maxLen as public and update them as extension going on.但是这题会有follow up：当需要找longest palindromic subsequence的时候，就需要用dynamic programming了。

代码：

int lo = 0;
int maxLen = 0;
public String longestPalindrome(String s) {
    if(s == null || s.length() <= 1){
        return s;
    }
    int len = s.length();
    for(int i = 0; i <= len - 2; i++){
        extend(s, i, i);
        extend(s, i, i + 1);
    }
    return s.substring(lo, lo + maxLen);
}
private void extend(String s, int left, int right) {
    while(left >= 0 && right <= s.length() - 1 && s.charAt(left) == s.charAt(right)){
        left--;
        right++;
    }
    if(maxLen < right - left - 1){
        lo = left + 1;
        maxLen = right - left - 1;
    }
}

longest palindromic subsequence：

public int longestPalindromeSubseq(String s) {
    int len = s.length();
    int[][] dp = new int[len][len];
    for(int i = 0; i <= len - 1; i++){
        dp[i][i] = 1;
        for(int j = i - 1; j >= 0; j--){
            if(s.charAt(i) ==s.charAt(j)){
                dp[i][j] = dp[i - 1][j + 1] + 2;
            }
            else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j + 1]);
            }
        }
    }
    return dp[len - 1][0];
}