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".

また、制約は、 が小文字の英語文字で構成されることを示します。

---

前の問題では、指定された文字列内で最長の回文部分文字列を見つける解決策が見つかりました。回文を見つけるために、各文字を部分文字列の中央の文字として想定する「中心上に展開」アプローチを使用しました。それに応じて、左右のポインターを移動しました。

Note

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

1 つの部分文字列内の回文を数えると次のようになります:

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;
}

範囲 (left >= 0 && right < s.length) 内にある限り、左右の 2 つの文字が同じかどうかを確認します。同じであれば、結果を更新し、結果をシフトします。ポインタ。

しかし、よく考えてみると、ポインタがどのインデックスで初期化されるかが重要になります。たとえば、文字列「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 中国語 Web サイトの他の関連記事を参照してください。