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]