文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 自己寫的DP
    • 2.2 優化后的DP
    • 2.3 中心擴展法

1. 題目

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

示例 1： 輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案。示例 2： 輸入: "cbbd" 輸出: "bb"

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 類似題目：

LeetCode 1216. 驗證回文字符串 III（DP）
LeetCode 1312. 讓字符串成為回文串的最少插入次數（區間DP）
LeetCode 647. 回文子串（DP）
LeetCode 516. 最長回文子序列（動態規劃）

2.1 自己寫的DP

• 自己寫的DP，效率比較差，$O(n^2)$ 時間復雜度
• 從長度1開始遍歷子串長度，具體見注釋

class Solution { public:string longestPalindrome(string s) {int i, j, len, n = s.size(), maxLen = 0;if(n <= 1)return s;string ans;vector<vector<int>> dp(n,vector<int>(n,0));vector<vector<bool>> same(n,vector<bool>(n,false));//表示區間[i,j]的最大回文長度for(i = 0; i < n; ++i){dp[i][i] = 1;//單個字符是回文same[i][i] = true;//區間內字符都一樣嗎}for(len = 1; len < n; ++len){for(i = 0; i < n-len; ++i){if(dp[i][i+len-1])//【i,i+len-1】是回文串{if(same[i][i+len-1])//區間內都一樣{ //奇數個字符的回文---> +1變偶數長度(必須區間內全相等)//偶數個字符的回文---> +1變奇數長度(必須區間內全相等)if(i-1 >= 0){if(s[i-1]==s[i+len-1])//左邊增加1個字符{dp[i-1][i+len-1] = 1 + dp[i][i+len-1];same[i-1][i+len-1] = true;}if(s[i-1]==s[i+len])//左右各增加1個{if(s[i-1]==s[i])same[i-1][i+len] = true;dp[i-1][i+len] = 2 + dp[i][i+len-1];}}if(s[i+len]==s[i])//右邊增加1個{dp[i][i+len] = 1 + dp[i][i+len-1];same[i][i+len] = true;}}else//區間[i, i+len-1]內字符不一樣,只能+2個字符上來{if(i-1>=0 && s[i-1]==s[i+len])dp[i-1][i+len] = 2 + dp[i][i+len-1];}}if(i-1>=0){if(dp[i-1][i+len-1] > maxLen){maxLen = dp[i-1][i+len-1];ans = s.substr(i-1,maxLen);}if(dp[i-1][i+len] > maxLen){maxLen = dp[i-1][i+len];ans = s.substr(i-1,maxLen);}}if(dp[i][i+len-1] > maxLen){maxLen = dp[i][i+len-1];ans = s.substr(i,maxLen);}if(dp[i][i+len] > maxLen){maxLen = dp[i][i+len];ans = s.substr(i,maxLen);}}}return ans;} };

1440 ms 202.3 MB，擊敗了 5% cpp

2.2 優化后的DP

• 在上面基礎上，初始化的時候把1個字符，2個字符的回文都先找出來

class Solution { public:string longestPalindrome(string s) {if(s.size() <= 1)return s;int i, j, len, n = s.size(), maxLen = 1;string ans = s.substr(0,1);vector<vector<bool>> dp(n,vector<bool>(n,0));for(i = 0; i < n; ++i){dp[i][i] = true;if(i < n-1 && s[i]==s[i+1]){dp[i][i+1] = true;if(maxLen < 2){maxLen = 2;ans = s.substr(i,2);}}}for(len = 1; len < n; ++len){for(i = 0; i < n-len; ++i){if(dp[i][i+len-1] && i-1>=0 && s[i-1]==s[i+len])//是回文串{dp[i-1][i+len] = true;if(len+2 > maxLen){maxLen = len+2;ans = s.substr(i-1,maxLen);}}}}return ans;} };

716 ms 24.8 MB

2.3 中心擴展法

• 有2n+1個中心，包括兩個字符之間

class Solution { public:string longestPalindrome(string s) {if(s.size() <= 1)return s;int i, j, len, len1, len2, n = s.size(), maxLen = 0;string ans;for(i = 0; i < n; ++i){len1 = centerspand(s,i,i);len2 = centerspand(s,i,i+1);len = max(len1,len2);if(len > maxLen){maxLen = len;ans = s.substr(i-(len-1)/2, len);}}return ans;}int centerspand(string& s, int l, int r){int len = 0;if(l==r)len++,l--,r++;while(l>=0 && r<s.size() && s[l]==s[r]){len += 2;l--;r++;}return len;} };

60 ms 10.5 MB

總結

以上是生活随笔為你收集整理的LeetCode 5. 最长回文子串（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。