Meditasi LeetCode: Substrings Palindromic

Penerangan untuk Subrentetan Palindromik ialah:

Diberi rentetan s, kembalikan bilangan subrentetan palindromik di dalamnya.

Rentetan ialah palindrom apabila ia dibaca sama ke belakang dengan ke hadapan.

subrentetan ialah jujukan aksara bersebelahan dalam rentetan.

Contohnya:

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

Atau:

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

Selain itu, kekangan menunjukkan bahawa s terdiri daripada huruf Inggeris huruf kecil.

---

Dalam masalah sebelumnya, kami menemui penyelesaian untuk mencari subrentetan palindromik terpanjang dalam rentetan tertentu. Untuk mencari palindrom, kami menggunakan pendekatan "kembangkan ke tengah", di mana kami menganggap setiap aksara sebagai watak tengah subrentetan. Dan, sewajarnya, kami mengalihkan penunjuk kiri dan kanan.

Note

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

Mengira palindrom dalam satu subrentetan mungkin kelihatan seperti ini:

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

Selagi kami berada dalam sempadan (kiri >= 0 && kanan < s.length), kami menyemak sama ada dua aksara di kiri dan kanan adalah sama — jika ya, kami mengemas kini keputusan kami dan mengalihkan petunjuk.

Walau bagaimanapun, sebaik sahaja anda memikirkannya, adalah penting di mana indeks penunjuk dimulakan. Sebagai contoh, jika kita menghantar rentetan "abc" kepada countPalindromesInSubstr, dan penunjuk kiri berada pada 0 manakala penunjuk kanan berada pada indeks terakhir (2), maka keputusan kita hanyalah 0.

Ingat bahawa kami menganggap setiap aksara sebagai aksara tengah subrentetan, dan memandangkan setiap aksara tunggal juga merupakan subrentetan, kami akan memulakan penunjuk kiri dan kanan kami untuk menunjuk kepada aksara itu sendiri.

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.

Atas ialah kandungan terperinci Meditasi LeetCode: Substrings Palindromic. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!