# 0005. 最長回文子串 ## 題目地址（5. 最長回文子串） <https://leetcode-cn.com/problems/longest-palindromic-substring/> ## 題目描述 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。 示例 1： 輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案。 示例 2： 輸入: "cbbd" 輸出: "bb" ## 前置知識 - 回文 ## 公司 - 阿里 - 百度 - 騰訊 ## 思路 這是一道最長回文的題目，要我們求出給定字符串的最大回文子串。  解決這類問題的核心思想就是兩個字“延伸”，具體來說 - 如果在一個不是回文字符串的字符串兩端添加任何字符，或者在回文串左右分別加不同的字符，得到的一定不是回文串 - 如果一個字符串不是回文串，或者在回文串左右分別加不同的字符，得到的一定不是回文串 事實上，上面的分析已經建立了大問題和小問題之間的關聯， 基于此，我們可以建立動態規劃模型。 我們可以用 dp\[i\]\[j\] 表示 s 中從 i 到 j（包括 i 和 j）是否可以形成回文， 狀態轉移方程只是將上面的描述轉化為代碼即可： ``` <pre class="calibre18">``` <span class="hljs-keyword">if</span> (s[i] === s[j] && dp[i + <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>]) { dp[i][j] = <span class="hljs-params">true</span>; } ``` ```  base case 就是一個字符（軸對稱點是本身），或者兩個字符（軸對稱點是介于兩者之間的虛擬點）。  ## 關鍵點 - ”延伸“（extend） ## 代碼 代碼支持：Python，JavaScript： Python Code： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPalindrome</span><span class="hljs-params">(self, s: str)</span> -> str:</span> n = len(s) <span class="hljs-keyword">if</span> n == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-string">""</span> res = s[<span class="hljs-params">0</span>] <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">extend</span><span class="hljs-params">(i, j, s)</span>:</span> <span class="hljs-keyword">while</span>(i >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> j < len(s) <span class="hljs-keyword">and</span> s[i] == s[j]): i -= <span class="hljs-params">1</span> j += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> s[i + <span class="hljs-params">1</span>:j] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">1</span>): e1 = extend(i, i, s) e2 = extend(i, i + <span class="hljs-params">1</span>, s) <span class="hljs-keyword">if</span> max(len(e1), len(e2)) > len(res): res = e1 <span class="hljs-keyword">if</span> len(e1) > len(e2) <span class="hljs-keyword">else</span> e2 <span class="hljs-keyword">return</span> res ``` ``` JavaScript Code： ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=5 lang=javascript * * [5] Longest Palindromic Substring */</span> <span class="hljs-title">/** * @param {string} s * @return {string} */</span> <span class="hljs-keyword">var</span> longestPalindrome = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s</span>) </span>{ <span class="hljs-title">// babad</span> <span class="hljs-title">// tag : dp</span> <span class="hljs-keyword">if</span> (!s || s.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>; <span class="hljs-keyword">let</span> res = s[<span class="hljs-params">0</span>]; <span class="hljs-keyword">const</span> dp = []; <span class="hljs-title">// 倒著遍歷簡化操作， 這么做的原因是dp[i][..]依賴于dp[i + 1][..]</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = s.length - <span class="hljs-params">1</span>; i >= <span class="hljs-params">0</span>; i--) { dp[i] = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = i; j < s.length; j++) { <span class="hljs-keyword">if</span> (j - i === <span class="hljs-params">0</span>) dp[i][j] = <span class="hljs-params">true</span>; <span class="hljs-title">// specail case 1</span> <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (j - i === <span class="hljs-params">1</span> && s[i] === s[j]) dp[i][j] = <span class="hljs-params">true</span>; <span class="hljs-title">// specail case 2</span> <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (s[i] === s[j] && dp[i + <span class="hljs-params">1</span>][j - <span class="hljs-params">1</span>]) { <span class="hljs-title">// state transition</span> dp[i][j] = <span class="hljs-params">true</span>; } <span class="hljs-keyword">if</span> (dp[i][j] && j - i + <span class="hljs-params">1</span> > res.length) { <span class="hljs-title">// update res</span> res = s.slice(i, j + <span class="hljs-params">1</span>); } } } <span class="hljs-keyword">return</span> res; }; ``` ``` ***復雜度分析*** - 時間復雜度：O(N2)O(N^2)O(N2) - 空間復雜度：O(N2)O(N^2)O(N2) ## 相關題目 - [516.longest-palindromic-subsequence](516.longest-palindromic-subsequence.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。