LeetCode 冥想：回文子串

回文子字串的描述是：

給定一個字串 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;
}

Time and space complexity

The time complexity is $O(n^2)$O(n2) as we go through each substring for each character (countPalindromes is doing an $O(n^2)$O(n2) operation, we call it twice separately.)
The space complexity is $O(1)$O(1) as we don't have an additional data structure whose size will grow with the input size.

---

Next up is the problem called Decode Ways. Until then, happy coding.

以上是LeetCode 冥想：回文子串的詳細內容。更多資訊請關注PHP中文網其他相關文章！