5. 最長迴文子串
- 2019 年 10 月 4 日
- 筆記
題目描述
給定一個字元串 s,找到 s 中最長的迴文子串。你可以假設 s 的最大長度為 1000。
示例 1:
輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個有效答案。
示例 2:
輸入: "cbbd" 輸出: "bb"
來源:力扣(LeetCode) 鏈接:https://leetcode-cn.com/problems/longest-palindromic-substring 著作權歸領扣網路所有。商業轉載請聯繫官方授權,非商業轉載請註明出處。
思路
這是一道最長迴文的題目,要我們求出給定字元串的最大迴文子串。
解決這類問題的核心思想就是兩個字「延伸」,具體來說
- 如果一個字元串是迴文串,那麼在它左右分別加上一個相同的字元,那麼它一定還是一個迴文串
- 如果一個字元串不是迴文串,或者在迴文串左右分別加不同的字元,得到的一定不是迴文串
事實上,上面的分析已經建立了大問題和小問題之間的關聯, 基於此,我們可以建立動態規劃模型。
我們可以用 dp[i][j] 表示 s 中從 i 到 j(包括 i 和 j)是否可以形成迴文, 狀態轉移方程只是將上面的描述轉化為程式碼即可:
if (s[i] === s[j] && dp[i + 1][j - 1]) { dp[i][j] = true; }
base case就是一個字元(軸對稱點是本身),或者兩個字元(軸對稱點是介於兩者之間的虛擬點)。
關鍵點
- 」延伸「(extend)
程式碼
/* * @lc app=leetcode id=5 lang=javascript * * [5] Longest Palindromic Substring */ /** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { // babad // tag : dp if (!s || s.length === 0) return ""; let res = s[0]; const dp = []; // 倒著遍歷簡化操作, 這麼做的原因是dp[i][..]依賴於dp[i + 1][..] for (let i = s.length - 1; i >= 0; i--) { dp[i] = []; for (let j = i; j < s.length; j++) { if (j - i === 0) dp[i][j] = true; // specail case 1 else if (j - i === 1 && s[i] === s[j]) dp[i][j] = true; // specail case 2 else if (s[i] === s[j] && dp[i + 1][j - 1]) { // state transition dp[i][j] = true; } if (dp[i][j] && j - i + 1 > res.length) { // update res res = s.slice(i, j + 1); } } } return res; };
相關題目
- [516.longest-palindromic-subsequence]