5 - Longest Palindromic Substring

#medium

Given a string s, return the longest palindromicsubstring in s.

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

Solution

一個回文去掉頭尾兩頭，皆為回文。

1. 對角線皆為迴文。
2. 先處理列，再處理行。
3. dp[i][j] 表示字串s[i..j] 是否為迴文。
4. 轉移方程: dp[i][j] = ( s[i] == s[j] && dp[i+1][j-1])
5. 邊界條件: j - i < 3 => 邊界長度為2及3，不需要狀態轉移(當s[i][j]為相同時，就為迴文)
6. O(n方)

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if ( s.size() == 1 ) return s;
        int maxLen = 1, begin = 0;
        int left = 0;
        vector<vector<bool>> dp( len, vector<bool>( len, false ) );
        // 對角線皆為迴文
        for ( int i = 0; i < len; i++ ) {
           dp[i][i] = true;
        }    

        for ( int j = 1; j < len; j++ ) {
            for ( int i = 0; i < j; i++ ) {
              if ( s[i] != s[j] ) dp[i][j] = false;
              else {
                if ( j - i < 3 ) {
                    dp[i][j] = true;
                }
                else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }

                if ( dp[i][j] && j - i + 1 > maxLen ) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            
            }
        }

        return s.substr( begin, maxLen );
    }
};