0647. 回文子串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 中心扩展

1. 📝 题目描述

• leetcode

给你一个字符串 s，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

---

示例 1：

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

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

---

提示：

• 1 <= s.length <= 1000
• s 由小写英文字母组成

2. 🎯 s.1 - 中心扩展

c

int countSubstrings(char* s) {
    int n = strlen(s), count = 0;
    for (int i = 0; i < n; i++) {
        int l = i, r = i;
        while (l >= 0 && r < n && s[l] == s[r]) { count++; l--; r++; }
        l = i; r = i + 1;
        while (l >= 0 && r < n && s[l] == s[r]) { count++; l--; r++; }
    }
    return count;
}

js

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function (s) {
  let count = 0
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      count++
      l--
      r++
    }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i)
    expand(i, i + 1)
  }
  return count
}

py

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        for i in range(n):
            l, r = i, i
            while l >= 0 and r < n and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1
            l, r = i, i + 1
            while l >= 0 and r < n and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1
        return count

• 时间复杂度：$O(n^2)$，其中 n 是字符串长度
• 空间复杂度：$O(1)$

算法思路：

• 枚举每个位置作为回文中心，分别处理奇数长度和偶数长度的回文
• 向两侧扩展，每次匹配时计数加 1