My Muri Life

切换主题

本页目录

回文问题篇 ​

回文子串 ​

剑指 Offer II 020. 回文子串

中心扩散法！

JavaScript
const countSubstrings = s => {
  const len = s.length
  let cnt = 0
  for (let idx = 0; idx < 2 * len - 1; idx++) {
    let [i, j] = [idx >> 1, (idx >> 1) + (idx & 1)]
    while (i >= 0 && j < len) {
      if (s.charAt(i) !== s.charAt(j)) break
      cnt++
      i--
      j++
    }
  }
  return cnt
}

时间复杂度：O(n^2)；空间复杂度：O(1)。

最长回文子串 ​

5. 最长回文子串

中心扩散法！

JavaScript
const longestPalindrome = s => {
  const len = s.length
  let max = start = end = 0
  for (let idx = 0; idx < 2 * len - 1; idx++) {
    let [i, j] = [idx >> 1, (idx >> 1) + (idx & 1)]
    while (i >= 0 && j < len) {
      if (s.charAt(i) !== s.charAt(j)) break
      if (j - i > max) {
        max = j - i
        start = i
        end = j
      }
      i--
      j++
    }
  }
  return s.substring(start, end + 1)
}

时间复杂度：O(n^2)；空间复杂度：O(1)。

分割回文串 ​

剑指 Offer II 086. 分割回文串

分割回文串 II ​

剑指 Offer II 094. 分割回文串 II

  • 状态定义：dp[i] = x，表示s[0]至s[i-1]的最小切割次数为x；
  • base case：dp[0] = -1；
  • 状态转移方程：dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1)。
JavaScript
const minCut = s => {
  const len = s.length
  const dp = Array(len + 1).fill(Infinity)
  dp[0] = -1
  for (let idx = 0; idx < 2 * len - 1; idx++) {
    let [i, j] = [idx >> 1, (idx >> 1) + (idx & 1)]
    while (i >= 0 && j < len) {
      if (s.charAt(i) !== s.charAt(j)) break
      dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1)
      i--
      j++
    }
  }
  return dp[len]
}

时间复杂度：O(n^2)；空间复杂度：O(n)。