Méditations LeetCode : sous-chaînes palindromiques

La description des sous-chaînes palindromiques est la suivante :

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

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 nos pointeurs.

Cependant, une fois que vous y réfléchissez, il est important de savoir sur quels indices les pointeurs sont initialisés. 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.

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.

以上是Méditations LeetCode : sous-chaînes palindromiques的详细内容。更多信息请关注PHP中文网其他相关文章！