palindromic-substrings.md

647. Palindromic Substrings - 回文子串

Tags - 题目标签

Description - 题目描述

EN:

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

ZH-CN:

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

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	64 ms	42.9 MB	2023/08/12 22:43

function countSubstrings(s: string): number {
  if (s.length === 1) {
    return 1;
  }

  let count = 0;

  for (let i = 0; i < s.length; i++) {
    // 长度为奇数情况
    for (let j = 0; i + j <= s.length && i - j >= 0; j++) {
      if (s[i - j] === s[i + j]) {
        count += 1;
      } else {
        break;
      }
    }

    // 长度为偶数情况
    for (let j = 0; i + j <= s.length && i - j >= 0; j++) {
      if (s[i - j] === s[i + j + 1]) {
        count += 1;
      } else {
        break;
      }
    }
  }

  return count;
};

My Notes - 我的笔记

中心展开法

回文串，沿着中心展开，分奇偶讨论。

function countSubstrings(s: string): number {
  if (s.length === 1) {
    return 1;
  }

  let count = 0;

  for (let i = 0; i < s.length; i++) {
    // 长度为奇数情况
    for (let j = 0; i + j <= s.length && i - j >= 0; j++) {
      if (s[i - j] === s[i + j]) {
        count += 1;
      } else {
        break;
      }
    }

    // 长度为偶数情况
    for (let j = 0; i + j <= s.length && i - j >= 0; j++) {
      if (s[i - j] === s[i + j + 1]) {
        count += 1;
      } else {
        break;
      }
    }
  }

  return count;
};