Méditations LeetCode : sous-chaînes palindromiques

La description des sous-chaînes palindromiques est :

Étant donné une chaîne s, renvoie le nombre de sous-chaînes palindromiques qu'elle contient.

Une chaîne est un palindrome lorsqu'elle se lit de la même manière vers l'arrière et vers l'avant.

Une sous-chaîne est une séquence contiguë de caractères dans la chaîne.

Par exemple :

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

Ou :

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

De plus, les contraintes indiquent que s est constitué de lettres anglaises minuscules.

---

Dans le problème précédent, nous avons trouvé une solution pour trouver la sous-chaîne palindromique la plus longue dans une chaîne donnée. Pour trouver un palindrome, nous avons utilisé une approche « développer par-dessus le centre », dans laquelle nous avons supposé que chaque caractère était le caractère central d'une sous-chaîne. Et, en conséquence, nous avons décalé les pointeurs gauche et droit.

Note

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

Compter les palindromes dans une sous-chaîne peut ressembler à ceci :

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

Tant que nous sommes dans les limites (gauche >= 0 && droite < s.length), nous vérifions si deux caractères à gauche et à droite sont identiques — si c'est le cas, nous mettons à jour notre résultat et décalons notre pointeurs.

Cependant, une fois que vous y réfléchissez, les indices sur lesquels les pointeurs sont initialisés sont importants. Par exemple, si nous passons la chaîne "abc" à countPalindromesInSubstr et que le pointeur gauche est à 0 tandis que le pointeur droit est au dernier index (2), alors notre résultat est simplement 0.

N'oubliez pas que nous supposons que chaque caractère est le caractère central d'une sous-chaîne, et comme chaque caractère est également une sous-chaîne, nous initialiserons nos pointeurs gauche et droit pour qu'ils pointent vers le caractère lui-même.

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.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!