回文子串的描述是：
给定一个字符串 s，返回其中回文子串的数量.当向后读与向前读相同时，字符串是回文。a 子字符串 是字符串中连续的字符序列。
例如：
input: s = "abc"output: 3explanation: three palindromic strings: "a", "b", "c".
或者：
input: s = "aaa"output: 6explanation: 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’，’b’和’c’。
让我们看看这个过程是什么样的。
如果我们有字符串“abc”，我们首先假设“a”是子字符串的中间：
"abc"left = 0right = 0currentsubstr = 'a'totalpalindromes = 1 // a single character is a palindrome
然后，我们尝试扩展子字符串，看看 ‘a’ 是否可以成为另一个子字符串的中间字符：
"abc"left = -1right = 1currentsubstr = undefinedtotalpalindromes = 1
现在我们的左指针超出了界限，我们可以跳转到下一个字符：
"abc"left = 1right = 1currentsubstr = 'b'totalpalindromes = 2
现在，我们将更新我们的指针，事实上，’b’ 可以是另一个子字符串的中间字符：
s = "abc"left = 0right = 2currentsubstr = 'abc'totalpalindromes = 2
嗯，currentsubstr 不是回文。现在我们再次更新我们的指针：
梅子Ai论文
无限免费生成千字论文大纲-在线快速生成论文初稿-查重率10%左右
66 查看详情
s = "abc"left = -1right = 3currentsubstr = undefinedtotalpalindromes = 2
而且，我们又出界了。是时候继续下一个角色了：
s = "abc"left = 2right = 2currentsubstr = 'c'totalpalindromes = 3
移动指针，我们又出界了：
s = "abc"left = 1right = 3currentsubstr = undefinedtotalpalindromes = 3
现在我们已经遍历了每个字符，在本例中，总回文数的最终结果是 3。这意味着“abc”中有 3 个回文子串。
但是，有一个重要的警告：每次我们假设一个字符作为中间并初始化其左侧和右侧的两个指针时，我们都试图只找到奇数长度的回文。为了缓解这种情况，我们可以不考虑单个字符作为中间，而是考虑两个字符作为中间并像之前那样展开。
在这种情况下，查找偶数长度子串回文的过程将如下所示 – 最初，我们的右指针为 left + 1：
s = "abc"left = 0right = 1currentsubstr = 'ab'totalpalindromes = 0
然后，我们将更新我们的指针：
s = "abc"left = -1right = 2currentsubstr = undefinedtotalpalindromes = 0
超出范围。进入下一个角色：
s = "abc"left = 1right = 2currentsubstr = 'bc'totalpalindromes = 0
更新我们的指针：
s = "abc"left = 0right = 3currentsubstr = undefinedtotalpalindromes = 0
右指针超出范围，所以我们继续下一个字符：
s = "abc"left = 2right = 3currentsubstr = undefinedtotalpalindromes = 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 = 0 && right < s.length && s[left] === s[right]) { result++; left--; right++; } return result;}
时间和空间复杂度
时间复杂度为 o(n2)o(n^2) o(n 2 ） 当我们遍历每个字符的每个子字符串时（countpalindromes 正在做一个 o(n2)o(n^2) o(n 2 ） 操作，我们分别调用两次。）
空间复杂度为 o(1)o(1) o(1) 因为我们没有额外的数据结构，其大小会随着输入大小而增长。
接下来是名为“解码方式”的问题。在那之前，祝您编码愉快。
以上就是LeetCode 冥想：回文子串的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/468819.html
微信扫一扫 
支付宝扫一扫 
