跳到主要内容

动态规划 | 子序列

回文

主要涉及回文系列

回文子串 647

LeetCode 647. 回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

Q & A

解法 1

动态规划

思路
  1. 状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
  2. 状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false(false 也不需要处理，在这里，dp 初始化的时候全部为 false)

当 s[i] == s[j] 时可能 j - i < 2 的所以可能形成字符串 a aa 这也是回文字符串，是满足条件的

当 s[i] == s[j] 时 j - i > 2，这个时候就需要考虑记忆化判断上次是否是回文字符串，也就是 dp[i + 1][j - 1] 是否为true

var countSubstrings = function(s) {
  const n = s.length
  const dp = Array.from({length: n}, (v, i) => new Array(n).fill(false))

  let count = 0

  for (let i = n - 1; i >=0; i --) {
    const si = s[i]
    for (let j = i; j < n; j ++) {
      const sj= s[j]
      // 如果s[i] = s[j] 表示是回文字符串
      // 如果 j - i < 2 表示 a 和 aa 都是回文字符串
      // 其他情况根据记忆化满足条件,因为上一个是 true
      if (si === sj && (j - i < 2 || dp[i + 1 ][j - 1])) {
        dp[i][j] = true
        count ++
      }
    }
  }
  return count
};

解法二

中心扩散法

思路
  1. 依次选取中心点进行扩散
  2. 扩散可能中心点是 1 个或者是 2 个，所以需要分别判断(三个可以由一个扩散一次得到，4 个可以由两个扩散一次得到)
  3. 做好容错
var countSubstrings = function(s) {
  // 中心扩散法
  let n = s.length, ret = 0

  for (let i = 0; i < n; i++) {
    // 单个字符扩散
    // 三个可以有一个扩散一次得到
    let l = i, r = i
    while (l >= 0 && r < n && s[l--] === s[r++]) ret++

    // 两个字符扩散
    // 四个字符可以由两个扩散一次得到
    l = i, r = i + 1
    while (l >= 0 && r < n && s[l--] === s[r++]) ret++
  }
  return ret
};

最长回文子序列 516

LeetCode 516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
思路
  1. 确定 dp table 以及 i j 含义； dp[i][j] 表示字符串 s[i, j] 闭区域
  2. 确定递推公式
    1. s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2
    2. s[i]与s[j]不同，加入s[j]的回文子序列长度为dp[i + 1][j]
    3. s[i]与s[j]不同，加入s[i]的回文子序列长度为dp[i][j - 1]
    4. s[i]与s[j]不同，那么dp[i][j]一定是取最大的, 就有 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
  3. 初始化 dp table，全部为 0 即可
    1. dp[i][j] = 1, 因为 dp[i][j] 是单个字符串，单个字符串一定是 1
  4. 确定遍历循序，自下而上，自左往右，这样保证每一个下边的数据都是已经计算过的，可以直接用

Q & A

var longestPalindromeSubseq = function(s) {
  const n = s.length
  // 初始化dp
  const dp = Array.from({length: n}, (v,i) => new Array(n).fill(0))

  for (let i = n - 1; i >=0; i --) {
    dp[i][i] = 1
    const si = s[i]
    for (let j = i + 1; j < n; j ++) {
      const sj = s[j]

      // 如果当前字符相等，则取 dp[i + 1][j - 1] 字符的最长回文子序列加 2
      if (si == sj) dp[i][j] = dp[i + 1][j - 1] + 2
      // 不相等则取 dp[i + 1][j] 和 dp[i][j - 1] 中的最大值
      else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])

    }
  }
  return dp[0][n-1]
};

最长回文子串 5

LeetCode 5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"
思路
  1. 确定 dp table 以及 i j 含义； dp[i][j] 表示字符串 s[i, j] 闭区域
  2. 确定递推公式
    1. s[i]与s[j]相同, 需要检测 j - i < 2 或者 dp[i + 1][j - 1]
    2. j - i < 2 表示 a 和 aa 都是回文字符串
    3. dp[i + 1][j - 1] 表示之前上一个 s[i+1, j-1] 是回文字符串, 所以当前这个也是回文字符串
  3. 初始化 dp table，全部为 0 即可
  4. 确定遍历循序，自下而上，自左往右，这样保证每一个下边的数据都是已经计算过的，可以直接用

Q & A

var longestPalindrome = function (s) {
  let n = s.length;
  let res = '';
  let dp = Array.from(new Array(n), () => new Array(n).fill(0));

  for (let i = n - 1; i >= 0; i--) {
    const si = s[i]
    for (let j = i; j < n; j++) {
      const sj = s[j]

      // 当满足 si == sj 时，表示是回文字符串
      // 1. j - i < 2 表示 a 和 aa 都是回文字符串
      // 2. dp[i + 1][j - 1] 表示之前上一个 s[i+1, j-1] 是回文字符串, 所以当前这个也是回文字符串
      if (si == sj && (j - i < 2 || dp[i + 1][j - 1])) {
        dp[i][j] = 1
        // 判断新的回文字符串是否大于现有的回文字符串长度
        // 大于就拷贝更新最长回文字符串
        if (j - i + 1  > res.length) res = s.slice(i, j + 1)
      }
    }
  }
  return res;
};