LeetCode 冥想：回文子串-js教程-PHP中文网

LeetCode Meditations: Palindromic Substrings

回文子串的描述是：

给定一个字符串 s，返回其中回文子串的数量。当向后读与向前读相同时，字符串是回文。 子字符串是字符串中连续的字符序列。

例如：

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

登录后复制

或者：

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

登录后复制

此外，约束表明 s 由小写英文字母组成。

在上一个问题中，我们找到了找到给定字符串中最长回文子串的解决方案。为了找到回文，我们使用了“中心扩展”方法，其中我们假设每个字符都是子字符串的中间字符。因此，我们移动了左右指针。

Note
Checking a palindrome is easy with two pointers approach, which we've seen before with Valid Palindrome.

计算一个子串中的回文数可能如下所示：

function countPalindromesInSubstr(s: string, left: number, right: number): number {
  let result = 0;
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    result++;
    left--;
    right++;
  }

  return result;
}

登录后复制

只要我们在边界内（左 >= 0 && 右 < s.length），我们就会检查左右两个字符是否相同 - 如果是，我们会更新结果并移动我们的结果指点。但是，一旦您考虑一下，指针初始化的索引很重要。例如，如果我们将字符串“abc”传递给 countPalindromesInSubstr，并且左指针位于 0，而右指针位于最后一个索引 (2)，那么我们的结果就是 0。请记住，我们假设每个字符都是子字符串的中间字符，并且由于每个单个字符也是一个子字符串，因此我们将初始化左指针和右指针以指向字符本身。

Note
A character by itself is considered palindromic, i.e., "abc" has three palindromic substrings: 'a', 'b' and 'c'.

Let's see how this process might look like. If we have the string "abc", we'll first assume that 'a' is the middle of a substring:

"abc"

left = 0
right = 0
currentSubstr = 'a'

totalPalindromes = 1 // A single character is a palindrome

登录后复制

Then, we'll try to expand the substring to see if 'a' can be the middle character of another substring:

"abc"

left = -1
right = 1
currentSubstr = undefined

totalPalindromes = 1

登录后复制

Now that our left pointer is out of bounds, we can jump to the next character:

"abc"

left = 1
right = 1
currentSubstr = 'b'

totalPalindromes = 2

登录后复制

Now, we'll update our pointers, and indeed, 'b' can be the middle character of another substring:

s = "abc"

left = 0
right = 2
currentSubstr = 'abc'

totalPalindromes = 2

登录后复制

Well, currentSubstr is not a palindrome. Now we update our pointers again:

s = "abc"

left = -1
right = 3
currentSubstr = undefined

totalPalindromes = 2

登录后复制

And, we're out of bounds again. Time to move on to the next character:

s = "abc"

left = 2
right = 2
currentSubstr = 'c'

totalPalindromes = 3

登录后复制

Shifting our pointers, we'll be out of bounds again:

s = "abc"

left = 1
right = 3
currentSubstr = undefined

totalPalindromes = 3

登录后复制

Now that we've gone through each character, our final result of totalPalindromes is, in this case, 3. Meaning that there are 3 palindromic substrings in "abc". However, there is an important caveat: each time we assume a character as the middle and initialize two pointers to the left and right of it, we're trying to find only odd-length palindromes. In order to mitigate that, instead of considering a single character as the middle, we can consider two characters as the middle and expand as we did before. In this case, the process of finding the even-length substring palindromes will look like this — initially, our right pointer is left + 1:

s = "abc"

left = 0
right = 1
currentSubstr = 'ab'

totalPalindromes = 0

登录后复制

Then, we'll update our pointers:

s = "abc"

left = -1
right = 2
currentSubstr = undefined

totalPalindromes = 0

登录后复制

Out of bounds. On to the next character:

s = "abc"

left = 1
right = 2
currentSubstr = 'bc'

totalPalindromes = 0

登录后复制

Updating our pointers:

s = "abc"

left = 0
right = 3
currentSubstr = undefined

totalPalindromes = 0

登录后复制

The right pointer is out of bounds, so we go on to the next character:

s = "abc"

left = 2
right = 3
currentSubstr = undefined

totalPalindromes = 0

登录后复制

Once again we're out of bounds, and we're done going through each character. There are no palindromes for even-length substrings in this example.

We can write a function that does the work of counting the palindromes in each substring:

function countPalindromes(s: string, isOddLength: boolean): number {
  let result = 0;
  for (let i = 0; i < s.length; i++) {
    let left = i;
    let right = isOddLength ? i : i + 1;
    result += countPalindromesInSubstr(s, left, right);
  }

  return result;
}

登录后复制

In our main function, we can call countPalindromes twice for both odd and even length substrings, and return the result:

function countSubstrings(s: string): number {
  let result = 0;
  result += countPalindromes(s, true); // Odd-length palindromes
  result += countPalindromes(s, false); // Even-length palindromes

  return result;
}

登录后复制

Overall, our solution looks like this:

function countSubstrings(s: string): number {
  let result = 0;
  result += countPalindromes(s, true); // Odd-length palindromes
  result += countPalindromes(s, false); // Even-length palindromes

  return result;
}

function countPalindromes(s: string, isOddLength: boolean): number {
  let result = 0;
  for (let i = 0; i < s.length; i++) {
    let left = i;
    let right = isOddLength ? i : i + 1;
    result += countPalindromesInSubstr(s, left, right);
  }

  return result;
}

function countPalindromesInSubstr(s: string, left: number, right: number): number {
  let result = 0;
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    result++;
    left--;
    right++;
  }

  return result;
}

登录后复制