5. Longest Palindromic Substring

Description

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

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

Solution

• 暴力扩展
  遍历s，以s[i]为中心向左右扩展最长子串，注意aa和aba两种形式，时间复杂度O(n²)，空间O(1)

• 动态规划
  这种求最长最大且前后有一定依赖关系的题目，可以考虑从动态规划去切入，只需要搞定动规方程即可。
  维持二维数组dpVec，其中dpVec[i][j]表示子字符串s.substr(i, j-i+1)是否是回文串，则

                 i==j   //条件1
dp[i][j]  =      j==i+1 && s[i]==s[j]   //条件2
                 j>i+1 && s[i]==s[j] && dp[i+1][j-1]  //条件3

注意i、j的变化趋势，这样遍历一个二维数组的上三角即可求解

string longestPalindrome(string s) {
    int len = s.length();
    int begin = 0, maxLen = 0;
    vector<vector<bool> > dpVec(len, vector<bool>(len, false));
    for (int i=len-1; i>=0; --i) {
        for (int j=i; j<len; ++j) {
            if (i==j || (j==i+1 && s[i]==s[j]) || (j>i+1 && s[i]==s[j] && dpVec[i+1][j-1])) {
                dpVec[i][j] = true;
                if (j-i+1 > maxLen) {
                    begin = i;
                    maxLen = j - i + 1;
                }
            }
        }
    }
    return s.substr(begin, maxLen);
}