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 중국어 웹사이트의 기타 관련 기사를 참조하세요!