LeetCode 명상: 회문 부분 문자열-JS 튜토리얼-php.cn

LeetCode Meditations: Palindromic Substrings

回文部分文字列の説明は次のとおりです:

文字列 s を指定すると、その中の 回文部分文字列の数を返します. 文字列は、後ろから読んでも前から読んでも同じ場合、回文になります。部分文字列は、文字列内の連続した文字のシーケンスです。例:

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

注意回文のチェックは、Valid Palindrome で以前に見た 2 つのポインターのアプローチを使用すると簡単です。

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

リーリー範囲内 (left >= 0 && right < s.length) 内にある限り、左右の 2 つの文字が同じかどうかを確認します。同じであれば、結果を更新し、ポインタを移動します。しかし、よく考えてみると、ポインターがどのインデックスで初期化されるかが重要です。たとえば、文字列「abc」を countPalindromesInSubstr に渡し、左ポインタが 0 にあり、右ポインタが最後のインデックス (2) にある場合、結果は単純に 0 になります。各文字を部分文字列の中央の文字として想定していることに注意してください。また、それぞれの単一文字も部分文字列であるため、文字自体を指すように左右のポインタを初期化します。

注意文字自体は回文とみなされます。つまり、「abc」には 3 つの回文部分文字列「a」、「b」、「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: