[C++]LeetCode: 99 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, and there exists one unique longest palindromic substring.

思路：題目要求的s的一個最長回文子串。暴力解決辦法就是枚舉所有的子串，再對每個子串進行回文判斷。進行剪枝，我們考慮可以使用動態規劃來避免重復的判斷。

 

dp[i][j]表示s[i...j]是否是回文.初始化：dp[i][i] = true ( 0 <= i <= n-1) ; dp[i][i-1] = true (1 <= i <= n-1); 其余的初始化為false根據回文的規則，判定s[i...j] 是否是回文，如果是，需要s[i] == s[j] 並且dp[i+1][j-1] == true 。即遞推公式：dp[i][j] = (s[i] == s[j] && dp[i+1][j-1] == true) Attention: 1. 其他值初始化為false , 利用memset最初把所有值初始化false.

//dp[i][j]表示子串s[i...j]是否是回文
        bool dp[len][len];
        memset(dp, 0, sizeof(dp));

2. 初始化時需要初始化dp[i][i] 和dp[i][i-1]。第二個容易遺忘，但是後面會用到。

 dp[0][0] = true;
        for(int i = 1; i < len; i++)
        {
            dp[i][i] = true;
            dp[i][i-1] = true;  //容易遺忘的初始化，k = 2時，dp[i+1][i+k-2]要用到
        }

3. 題目要求返回最長的回文子串，所以我們要維護兩個變量，一個是最長回文的起點，還有它的長度。

 if(longlen < k)
                    {
                       retleft = i;
                       longlen = k;
                    }

4. 要想窮舉所有情況，我們外層循環枚舉所有的子字符串長度，內層循環枚舉字符串的所有起始位置。

for(int k = 2; k <= len; k++)   //枚舉子字符串的長度
        {
            for(int i = 0; i <= len - k; i++)  //枚舉子字符串的起始位置

復雜度：O(N^2) AC Code:

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() <= 1) return s;
        const int len = s.size();
        //dp[i][j]表示子串s[i...j]是否是回文
        bool dp[len][len];
        memset(dp, 0, sizeof(dp));
        
        //最長回文的起點和長度
        int retleft = 0;
        int longlen = 1;
        
        dp[0][0] = true;
        for(int i = 1; i < len; i++)
        {
            dp[i][i] = true;
            dp[i][i-1] = true;  //容易遺忘的初始化，k = 2時，dp[i+1][i+k-2]要用到
        }
        
        for(int k = 2; k <= len; k++)   //枚舉子字符串的長度
        {
            for(int i = 0; i <= len - k; i++)  //枚舉子字符串的起始位置
            {
                if(s[i] == s[i+k-1] && dp[i+1][i+k-2])
                {
                    dp[i][i+k-1] = true;
                    if(longlen < k)
                    {
                       retleft = i;
                       longlen = k;
                    }
                }
            }
        }
        
        return s.substr(retleft, longlen);
    }
};

這道題還有一個O(N)復雜度的解法：最長連續回文串（Longest Palindromic Substring）、