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

示例 1：

輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案。

示例 2：

輸入: "cbbd" 輸出: "bb"

dp[i][j]表示s[i]到s[j]所表示的子串是否是回文串，是則為1，不是則為0.根據s[i]是否等于s[j]，把轉移情況分為：

（1）若s[i]==s[j] 若s[i+1][j-1]要么是回文子串，那么s[i]至s[j]是回文子串，dp[i][j]=dp[i+1][j-1]，否則，dp[i][j] = 0。

（2）若s[i]==s[j]，則s[i]至s[j]不是回文子串,dp[i][j] = 0

class Solution {const int maxn = 1000+10; public:string longestPalindrome(string s) {int dp[maxn][maxn];int len = s.length();int start = 0, ans = 1;memset(dp,0,sizeof(dp));for(int i = 0; i < len; i++){dp[i][i] = 1; //長度為1的子串if(i<len-1){if(s[i] == s[i+1]) //長度為2的子串{dp[i][i+1] = 1;start = i;ans = 2;}}}for(int L = 3; L <= len; L++) //從長度為3的子串開始枚舉{for(int i = 0; i + L - 1 < len; i++) //起點{int j = i + L - 1; //右端點if(s[i] == s[j] && dp[i+1][j-1] == 1) //狀態轉移：{dp[i][j] = 1;start = i;ans = L;}}}return s.substr(start,ans);}};

?

總結

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

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