回文子串

回文子串

leetcode 链接

思路：

1. 确定 dp 数组定义, dp[i][j] 表示 s[i,j]子串是否为回文串

2. 初始化 dp 数组, 默认为 false

3. 确定遍历方向, 从后往前遍历

4. 确定转移方程, 如果 s[i] === s[j]，则如果 j - i <= 1, 则为 true，如果 j - i > 1, 则如果 i+1，j-1 为 true，则为 true

5. 返回 dp 数组中 true 的个数

typescript 解法

function countSubstrings(s: string): number {
  let dp = Array.from({ length: s.length }, () =>
    new Array(s.length).fill(false)
  );

  let result = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    for (let j = i; j < s.length; j++) {
      if (s[i] === s[j]) {
        if (j - i <= 1 || dp[i + 1][j - 1]) {
          result++;
          dp[i][j] = true;
        }
      }
    }
  }
  return result;
}

go 解法

func countSubstrings(s string) int {
    result := 0
    // 确定dp数组定义, dp[i][j] 表示s[i,j]子串是否为回文串
    dp := make([][]bool, len(s))
    for i := 0; i < len(s); i ++ {
        dp[i] = make([]bool, len(s))
    }
    // 初始化dp数组, 默认为false

    // 确定遍历方向
    for i := len(s) - 1; i >= 0; i -- {
        for j := i; j < len(s); j ++ {
            // 确定转移方程
            if s[i] == s[j] {
                // 情况1： i 和j 相等，为同一个字符，是回文子串
                // 情况2： j - i = 1, 相差一个字符，是回文子串
                if j - i <= 1 {
                    dp[i][j] = true
                    result ++
                    // 情况3： j - i > 1, 则如果i+1，j-1 为true，则为true
                } else if dp[i + 1][j - 1] {
                    dp[i][j] = true
                    result ++
                }
            } else {
                dp[i][j] = false
            }
        }
    }
    return result

}