回文子串

发表于2024-07-17更新于2024-07-17

回文子串

https://leetcode.cn/problems/palindromic-substrings/description/

图 0

思路

  • 1、dp[i][j] 表示以i开始，j结尾的字符串是否是回文子串
  • 2、递推公式：
    • if (s[i]==s[j])
      • if (i==j) return true
      • if (j-i==1) return true
      • if (j-i>1) return dp[i+1][j-1]
    • else dp[i][j] = false
  • 3、初始化：统统false
  • 4、遍历：i倒序，j正序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
超时了，129/132
var countSubstrings = function(s) {
  let num = 0
  function isHuiwen(t) {
    let p = 0;q = t.length-1
    while (p<q){
      if (t[p] != t[q]){
        return false
      }
      p++;
      q--
    }
    return true
  }
  for (let i=0;i<s.length;i++){
    for (let j=i+1;j<=s.length;j++){
      console.log(isHuiwen(s.substring(i, j)))
      if (isHuiwen(s.substring(i,j))) num ++
    }
  }
  return num
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
动态规划
var countSubstrings = function(s) {
  let num = 0
  let n = s.length
  let dp = Array.from({length:n},()=>Array(n).fill(false))
  for(let i=n-1;i>=0;i--){
    //j是尾巴，尾巴j大于等于头i
    for(let j=i;j<n;j++){
      if (s[i]==s[j]){
        if (j-i>1) {
          dp[i][j] = dp[i+1][j-1]
        }
        else dp[i][j] = true
      }
      if (dp[i][j] === true) num++
    }
  }
  console.log(dp)
  return num
};

最长回文子序列

https://leetcode.cn/problems/longest-palindromic-subsequence/description/

图 1

思路

  • 1、dp[i][j]表示 以i开头j结尾的字符串中最长回文子序列的长度
  • 2、递推公式：
    • if (s[i]==s[j]) dp[i][j] = dp[i+1][j-1]+2
    • else max(dp[i+1][j],dp[i][j-1]),分别把s[j]和s[i]加入后的最长回文子序列的长度。
  • 3、初始化：
  • 遍历顺序，i倒序，j正序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var longestPalindromeSubseq = function(s) {
  let n = s.length
  let dp = Array.from({length:n},()=>Array(n).fill(0))
  for (let i=0;i<n;i++){
    dp[i][i] =1
  }
  for(let i=n-1;i>=0;i--){
    for(let j=i+1;j<n;j++){
      if (i==j) dp[i][j] = 1
      if (s[i]==s[j]) dp[i][j] = dp[i+1][j-1] + 2
      else dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
    }
  }
  return dp[0][n-1]
};