LeetCode 冥想：回文子串

回文子串的描述是：

给定一个字符串 s，返回其中回文子串的数量. 当向后读与向前读相同时，字符串是回文。 a 子字符串 是字符串中连续的字符序列。

例如：

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 由小写英文字母组成。

在上一个问题中，我们找到了找到给定字符串中最长回文子串的解决方案。为了找到回文，我们使用了“中心扩展”方法，其中我们假设每个字符都是子字符串的中间字符。因此，我们移动了左右指针。

计算一个子串中的回文数可能如下所示：

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。

请记住，我们假设每个字符都是子字符串的中间字符，并且由于每个单个字符也是一个子字符串，因此我们将初始化左指针和右指针以指向字符本身。

让我们看看这个过程是什么样的。

如果我们有字符串“abc”，我们首先假设“a”是子字符串的中间：

"abc"

left = 0
right = 0
currentsubstr = 'a'

totalpalindromes = 1 // a single character is a palindrome

然后，我们尝试扩展子字符串，看看 'a' 是否可以成为另一个子字符串的中间字符：

"abc"

left = -1
right = 1
currentsubstr = undefined

totalpalindromes = 1

现在我们的左指针超出了界限，我们可以跳转到下一个字符：

"abc"

left = 1
right = 1
currentsubstr = 'b'

totalpalindromes = 2

现在，我们将更新我们的指针，事实上，'b' 可以是另一个子字符串的中间字符：

s = "abc"

left = 0
right = 2
currentsubstr = 'abc'

totalpalindromes = 2

嗯，currentsubstr 不是回文。现在我们再次更新我们的指针：

Tome

先进的AI智能PPT制作工具

下载

s = "abc"

left = -1
right = 3
currentsubstr = undefined

totalpalindromes = 2

而且，我们又出界了。是时候继续下一个角色了：

s = "abc"

left = 2
right = 2
currentsubstr = 'c'

totalpalindromes = 3

移动指针，我们又出界了：

s = "abc"

left = 1
right = 3
currentsubstr = undefined

totalpalindromes = 3

现在我们已经遍历了每个字符，在本例中，总回文数的最终结果是 3。这意味着“abc”中有 3 个回文子串。

但是，有一个重要的警告：每次我们假设一个字符作为中间并初始化其左侧和右侧的两个指针时，我们都试图只找到奇数长度的回文。为了缓解这种情况，我们可以不考虑单个字符作为中间，而是考虑两个字符作为中间并像之前那样展开。

在这种情况下，查找偶数长度子串回文的过程将如下所示 - 最初，我们的右指针为 left + 1：

s = "abc"

left = 0
right = 1
currentsubstr = 'ab'

totalpalindromes = 0

然后，我们将更新我们的指针：

s = "abc"

left = -1
right = 2
currentsubstr = undefined

totalpalindromes = 0

超出范围。进入下一个角色：

s = "abc"

left = 1
right = 2
currentsubstr = 'bc'

totalpalindromes = 0

更新我们的指针：

s = "abc"

left = 0
right = 3
currentsubstr = undefined

totalpalindromes = 0

右指针超出范围，所以我们继续下一个字符：

s = "abc"

left = 2
right = 3
currentsubstr = undefined

totalpalindromes = 0

我们再次出界，我们已经完成了每个角色。在这个例子中，偶数长度的子串没有回文。

我们可以编写一个函数来计算每个子串中的回文数：

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

在我们的 main 函数中，我们可以对奇数和偶数长度的子串调用两次 countpalindromes，并返回结果：

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

时间和空间复杂度

时间复杂度为css"> o(n2)o(n^2)o(n 2 ） 当我们遍历每个字符的每个子字符串时（countpalindromes 正在做一个 o(n2)o(n^2)o(n 2 ） 操作，我们分别调用两次。）
空间复杂度为 o(1)o(1)o(1) 因为我们没有额外的数据结构，其大小会随着输入大小而增长。

接下来是名为“解码方式”的问题。在那之前，祝您编码愉快。