5. Longest Palindromic Substring

Problem statement:

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.

Example:

Input: "cbbd"

Output: "bb"

Solution:

Compare with 516. Longest Palindromic Subsequence, the difference is the subsequence and substring, subsequence does not require all the palindrome is in a row, however, substring must be a consective string. The dynamic programming formula is a little bit different.

dp[i][j] meas s(i, j) is a palindrome or not, if it is the length is j - i + 1;

dp[i][j] is true only s[i] == s[j] and dp[i + 1][j - 1] also is true ( or i and j is consective or there is only one element between i and j).

Each time find a palindrome,  we should compare with previous one and update.

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        int dp[size][size] = {};
        string ans("");
        for(int i = size - 1; i >= 0; i--){
            for(int j = i; j < size; j++){
                if(s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1])){
                    dp[i][j] = 1;
                    if(ans.empty() || j - i + 1 > ans.size()){
                        ans = s.substr(i, j - i + 1);
                    }
                }
            }
        }
        return ans;
    }
};

5. Longest Palindromic Substring

原文：http://www.cnblogs.com/wdw828/p/6829000.html