本周繼續做一道動態規劃類型的題目，該題是阿里一面的一道算法題。

【動圖算法】(動態規劃篇)：最長回文子串

leetcode 5 題：最長回文子串
https://leetcode-cn.com/problems/longest-palindromic-substring/

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

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

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

解答過程

動態規劃-數組維護

var?longestPalindrome?=?function(s)?{
????let?n?=?s.length
????let?res?=?''
????//?初始化一個n*n的二維數組
????let?dp?=?Array.from(new?Array(n),()?=>?new?Array(n).fill(0))
????for(let?i?=?n-1;i?>=?0;i--){
????????for(let?j?=?i;j?????????????dp[i][j]?=?s[i]?==?s[j]?&&?(j?-?i?2?||?dp[i+1][j-1])
????????????if(dp[i][j]?&&?j?-?i?+1?>?res.length)
????????????????res?=?s.substring(i,j+1)
????????}
????}
????return?res
};

由動圖可以很清楚的看到：

• 首先初始化了一個n*n的二維數組
• 而后在循環中進行判斷：
  • 這里著重看 dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i+1][j-1])這里。
  • dp[i][j] = s[i] == s[j]判斷為當前項是否為回文。
  • j - i < 2 判斷其是否為最小奇偶字符串，即長度小于2
  • 若前一條不滿足，則判斷dp[i+1][j-1] 即其前一項是否依然為回文。

動態規劃-中心擴展

var?longestPalindrome?=?function(s)?{
????if(!s?||?s.length?2)?return?s
????let?start?=?0,end?=?0;
????let?n?=?s.length
????//?中心擴展法
????let?centerExpend?=?(left,right)?=>?{
????????while(left?>=?0?&&?right?????????????left--
????????????right++
????????}
????????return?right?-?left?-?1
????}
????for(let?i?=?0;i?????????let?len1?=?centerExpend(i,i)
????????let?len2?=?centerExpend(i,i+1)
????????let?maxLen?=?Math.max(len1,len2)
????????if(maxLen?>?end?-?start){
????????????//?這里的(maxLen?-?1)?>>?1即為對(maxLen-1)/2而后向下取整
????????????start?=?i?-?((maxLen?-?1)?>>?1)
????????????end?=?i?+?(maxLen?>>?1)
????????}
????}
????return?s.substring(start,end+1)
};

• 這里以i作為中心點，在for循環中len1與len2分別判斷了奇偶字符串是否為回文。
• 而后判斷長度，截取字符串

相較于前一種方法，該方法則更為簡單直觀：通過中心點向數組的兩端發散計算出回文的長度。最終得到正確的結果。

總結

以上是生活随笔為你收集整理的动态游标for循环_【【动图算法】（动态规划篇）：最长回文子串的全部內容，希望文章能夠幫你解決所遇到的問題。

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