回文子串

Tips

题目类型: 中心扩散法

相关题目:

• 5. 最长回文子串

题目

给定一个字符串, 你的任务是计算这个字符串中有多少个回文子串. 具有不同开始位置或结束位置的子串, 即使是由相同的字符组成, 也会被视作不同的子串.

示例

输入: 'abc'
输出: 3
解释: 三个回文子串: 'a', 'b', 'c'

输入: 'aaa'
输出: 6
解释: 六个回文子串: 'a', 'a', 'a', 'aa', 'aa', 'aaa'

题解

思路参考 5. 最长回文子串.

JavaScript

var countSubstrings = function (s) {
  let n = s.length
  let ans = 0

  for (let i = 0; i < 2 * n - 1; i++) {
    let left = (i / 2) | 0
    let right = left + (i % 2)

    while (left < n && right < n && s[left] === s[right]) {
      left--
      right++
      ans++
    }
  }

  return ans
}

Rust

pub fn count_substrings(s: String) -> i32 {
    let len = s.len();
    let center_count = len * 2 - 1;
    let s_byte = s.as_bytes();
    let mut ans = 0;

    for i in 0..center_count {
        let mut left = i / 2;
        let mut right = left + i % 2;

        // let left_el = s.chars().nth(left).unwrap();
        // let right_el = s.chars().nth(right).unwrap();

        while left < len && right < len && s_byte[left] == s_byte[right] {
            left -= 1;
            right += 1;
            ans += 1;
        }
    }

    ans
}

复杂度分析

• 时间复杂度: O(n²)
• 空间复杂度: O(n)