LeetCode【5】Longest Palindromic Substring

题目：

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

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

即给出一个字符串S，找到一个最长的连续回文串。

方法一：

简单易懂

class Solution {
int lo = 0, maxLen = 0;
public String longestPalindrome(String s) {
    for (int i = 0; i < s.length(); i++) {
        helper(s, i, i);
        helper(s, i, i + 1);
    }
    return s.substring(lo, lo + maxLen);
}

private void helper(String str, int l, int r) {
    while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r)) {
        l--;
        r++;
    }
    if (r - l - 1 > maxLen) {
        lo = l + 1;
        maxLen = r - l - 1;
    }
}
}

方法二：动态规划

这里动态规划的思路是 dp[i][j] 表示的是 从i 到 j 的字串，是否是回文串。
则根据回文的规则我们可以知道：
如果s[i] == s[j] 那么是否是回文决定于 dp[i+1][ j - 1]
当 s[i] != s[j] 的时候， dp[i][j] 直接就是 false。
动态规划的进行是按照字符串的长度从1 到 n推进的。
代码很明晰：给出java代码，复杂度 O(n^2)

public class Solution{
static boolean [][]dp;

public static String longestPalindrome(String s){
    if (s.length() == 0){
        return "";
    }
    if(s.length() == 1){
        return s;
    }

    dp = new boolean[s.length()][s.length()];

    for (int i = 0;i=j){
                dp[i][j] = true;
            }else {
                dp[i][j] = false;
            }
        }
    }

    int maxLen = 1;
    int rl = 0, rr = 0;
    for(int k = 1;kmaxLen){
                        maxLen = k+1;
                        rl = i;
                        rr = j;
                    }
                }
            }
        }
    }
    return s.substring(rl, rr+1);

}
}