題目描述
給你一個字符串 s，找到 s 中最長的回文子串。

示例 1：

輸入：s = “babad”
輸出：“bab”
解釋：“aba” 同樣是符合題意的答案。
示例 2：

輸入：s = “cbbd”
輸出：“bb”
示例 3：

輸入：s = “a”
輸出：“a”
示例 4：

輸入：s = “ac”
輸出：“a”

解題思路
1.理解什么是回文串。

• 如果一個字符串的頭尾兩個字符都不相等，那么這個字符串一定不是回文串；
• 如果一個字符串的頭尾兩個字符相等，才有必要繼續(xù)判斷下去。
  如果里面的子串是回文，整體就是回文串；
  如果里面的子串不是回文串，整體就不是回文串。
  即：在頭尾字符相等的情況下，里面子串的回文性質(zhì)據(jù)定了整個子串的回文性質(zhì)，這就是狀態(tài)轉(zhuǎn)移

第1步：定義狀態(tài)
dp[i][j] 代表 s[i…j]是否是回文子串，這里區(qū)間左閉右閉，表示s[i],s[j]可以取得到。
第 2 步：思考狀態(tài)轉(zhuǎn)移方程 dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

「動態(tài)規(guī)劃」事實上是在填一張二維表格，由于構(gòu)成子串，因此 i 和 j 的關(guān)系是 i <= j ，因此，只需要填這張表格對角線以上的部分。
看到dp[i+1][j-1] 就要考慮邊界問題
邊界條件就是[i+1，j-1] 不構(gòu)成區(qū)間，即長度嚴(yán)格小于 2，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3。
這個結(jié)論很顯然：j - i < 3 等價于 j - i + 1 < 4，即當(dāng)子串 s[i…j] 的長度等于 2 或者等于 3 的時候，其實只需要判斷一下頭尾兩個字符是否相等就可以直接下結(jié)論了。
如果子串 s[i + 1…j - 1] 只有 1 個字符，即去掉兩頭，剩下中間部分只有 1 個字符，顯然是回文；
如果子串 s[i + 1…j - 1] 為空串，那么子串 s[i, j] 一定是回文子串。
因此，在 s[i] == s[j] 成立和 j - i < 3 的前提下，直接可以下結(jié)論，dp[i][j] = true，否則才執(zhí)行狀態(tài)轉(zhuǎn)移。
第3步：初始化
初始化的時候，單個字符一定是回文串，因此把對角線先初始化為 true，即 dp[i][i] = true 。
如果是兩個字符的話，那dp[i][j] = (s[i] == s[j]),即兩個字符是相同的。
其他情況則是，dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]，保證兩頭的字符是相同的，然后中間的子串也是回文串。
注意：在狀態(tài)轉(zhuǎn)移方程中，我們是從長度較短的字符串向長度較長的字符串進行轉(zhuǎn)移的，因此一定要注意動態(tài)規(guī)劃的循環(huán)順序

代碼

class Solution { public:string longestPalindrome(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n));string ans; for(int l = 0;l< n;++l){for(int i = 0;i+l<n;++i){int j = i+l;if(l==0){dp[i][j] = 1;}else if(l==1){dp[i][j] = (s[i]==s[j]);}else{dp[i][j] = ((s[i]==s[j])&&dp[i+1][j-1]);}if(dp[i][j] && l+1 >ans.size()){/*substr(pos,len)*/ans = s.substr(i,l+1);}}}return ans;} };

Java

class Solution {public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];String ans = "";for(int l = 0; l < n;++l){for(int i=0;i+l < n;i++){int j = i+l;if(l==0){dp[i][j] = true;}else if(l==1){dp[i][j] = (s.charAt(i) == s.charAt(j));}else{dp[i][j] = ((s.charAt(i) == s.charAt(j)) && dp[i+1][j-1]);}if(dp[i][j]&&l+1>ans.length()){ans = s.substring(i,i+l+1);}}}return ans;} }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。