leetcode題解-5.最長回文子串

文章目錄

• 題目描述
• 思路解析
• 示例代碼

部落格專欄位址：https://blog.csdn.net/feng964497595/category_9848847.html

github位址：https://github.com/mufeng964497595/leetcode

題目描述

給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

思路解析

1. 首先，題目是求子串，不是子序列，這個注意一下~

2. 這題目見過挺多次了，字元串長度是1000，常見方法就是用動态規劃來處理：

   設 d p [ i ] [ j ] dp[i][j] dp[i][j]表示字元串s的子區間 [ i , j ] [i, j] [i,j]是否是回文數，那麼

   d p [ i ] [ j ] = { f a l s e , i > j t r u e , i == j d p [ i + 1 ] [ j − 1 ] , s[i] == s[j] && i+1 <= j-1 t r u e , s[i] == s[j] && i+1 > j-1 f a l s e , s[i]  ≠  s[j] dp[i][j] = \begin{cases} false, & \text{i > j} \\ true, & \text{i == j} \\ dp[i+1][j-1], & \text{s[i] == s[j] \&\& i+1 <= j-1} \\ true, & \text{s[i] == s[j] \&\& i+1 > j-1} \\ false, & \text{s[i] $\neq$ s[j]} \end{cases} dp[i][j]=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​false,true,dp[i+1][j−1],true,false,​i > ji == js[i] == s[j] && i+1 <= j-1s[i] == s[j] && i+1 > j-1s[i] ​= s[j]​

   這裡解析一下上面這條公式：

• 當 i > j i>j i>j時，顯然構不成字元串，直接置為false
• 當 i = = j i == j i==j時，字元串隻有一個字元，肯定是回文串
• 當 s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]，且 i + 1 < = j − 1 i+1 <= j-1 i+1<=j−1時，區間 [ i + 1 , j − 1 ] [i+1, j-1] [i+1,j−1]是有效字元串，如果這個字元串是回文串，那麼區間 [ i , j ] [i, j] [i,j]肯定也是；如果不是回文串，那區間 [ i , j ] [i, j] [i,j]也肯定不是，是以 d p [ i ] [ j ] = = d p [ i + 1 ] [ j − 1 ] dp[i][j] == dp[i+1][j-1] dp[i][j]==dp[i+1][j−1]
• 當 s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]，且 i + 1 > j − 1 i+1 > j-1 i+1>j−1時，即區間 [ i , j ] [i, j] [i,j]沒有子串了，又因為區間 [ i , j ] [i, j] [i,j]最多隻會有兩個字元，且 s [ i ] = = s [ j ] s[i] == s[j] s[i]==s[j]，是以區間 [ i , j ] [i, j] [i,j]是回文串
• 當 s [ i ] ≠ s [ j ] s[i] \neq s[j] s[i]​=s[j]，肯定就不會回文串

1. 當計算到 d p [ i ] [ j ] = t r u e dp[i][j] = true dp[i][j]=true時，更新此時的子串區間就可以了。為什麼不用記錄子串長度呢？因為題目沒要求哈哈哈哈哈哈哈，而且計算dp的時候，區間 [ i , j ] [i, j] [i,j]長度是遞增的，不會出現本次計算的回文串比上次計算出來的回文串短的情況，是以直接覆寫子串區間就好了。
2. 這裡要注意一下邊界情況：輸入的字元串是空串時，直接傳回空串即可。

示例代碼

class Solution {
public:
    string longestPalindrome(const string& s) {
        if (s.empty())
            return s;

        // 初始化
        bool dp[1005][1005];
        memset(dp, 0, sizeof(dp));
        int len = s.length();
        for (int i = 0; i < len; ++i)
            dp[i][i] = true;

        int start = 0, end = 0;
        for (int step = 1; step < len; ++step) {
            for (int i = 0; i < len; ++i) {
                int j = i + step;
                if (j >= len) break;

                if (s[i] == s[j] && (i+1 >= j-1 || dp[i+1][j-1])) {
                    // [i+1, j-1]就是一個回文串，且s[i]==s[j]，則[i, j]也是一個回文串
                    dp[i][j] = true;
                    start = i;
                    end = j;
                }
            }
        }

        return s.substr(start, end - start + 1);
    }
};