LeetCode-Meditationen: Palindromische Teilzeichenfolgen

Die Beschreibung für palindromische Teilzeichenfolgen lautet:

Gegebene Zeichenfolge s, gib die Anzahl der palindromischen Teilzeichenfolgen darin zurück.

Eine Zeichenfolge ist ein Palindrom, wenn sie rückwärts wie vorwärts dasselbe liest.

Eine Teilzeichenfolge ist eine zusammenhängende Folge von Zeichen innerhalb der Zeichenfolge.

Zum Beispiel:

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

Oder:

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

Außerdem weisen die Einschränkungen darauf hin, dass s aus englischen Kleinbuchstaben bestehen.

---

Im vorherigen Problem haben wir eine Lösung gefunden, um den längsten palindromischen Teilstring in einem gegebenen String zu finden. Um ein Palindrom zu finden, haben wir einen „Expand over Center“-Ansatz verwendet, bei dem wir jedes Zeichen als mittleres Zeichen einer Teilzeichenfolge annahmen. Und dementsprechend haben wir den linken und rechten Zeiger verschoben.

Note

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

Das Zählen der Palindrome in einem Teilstring könnte so aussehen:

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

Solange wir uns innerhalb der Grenzen befinden (links >= 0 && rechts < s.Länge), prüfen wir, ob zwei Zeichen links und rechts gleich sind – wenn ja, aktualisieren wir unser Ergebnis und verschieben unsere Hinweise.

Wenn Sie jedoch darüber nachdenken, ist es wichtig, bei welchen Indizes die Zeiger initialisiert werden. Wenn wir beispielsweise die Zeichenfolge „abc“ an countPalindromesInSubstr übergeben und der linke Zeiger auf 0 steht, während der rechte Zeiger auf dem letzten Index (2) steht, dann ist unser Ergebnis einfach 0.

Denken Sie daran, dass wir davon ausgehen, dass jedes Zeichen das mittlere Zeichen einer Teilzeichenfolge ist, und da jedes einzelne Zeichen auch eine Teilzeichenfolge ist, initialisieren wir unsere linken und rechten Zeiger so, dass sie auf das Zeichen selbst zeigen.

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.

Das obige ist der detaillierte Inhalt vonLeetCode-Meditationen: Palindromische Teilzeichenfolgen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!