文章目录647.回文子串题目思路代码实现Go5.最长回文子串题目思路代码实现Go:647.回文子串题目给你一个字符串 s 请你统计并返回这个字符串中回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。示例 1输入s “abc”输出3解释三个回文子串: “a”, “b”, “c”示例 2输入s “aaa”输出6解释6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”提示1 s.length 1000s 由小写英文字母组成思路题目要找字符串里所有连续的、正读反读一样的子串数量。回文串一定有中心点只有两种情况奇数长度中心点是 1 个字符如a、aba偶数长度中心点是 2 个相邻字符如aa、abba中心扩展法遍历字符串的每一个位置把它当作奇数回文中心遍历每一对相邻位置把它们当作偶数回文中心从中心往左右两边扩散只要左右字符相等就是一个回文每找到一个回文总数 1代码实现Gopackagemainimportfmt// expand 函数作用// 从给定的左指针 l、右指针 r 开始向左右两边扩展// 统计以 l、r 为中心的回文子串个数funcexpand(sstring,l,rint)int{// 记录本次扩展能找到的回文数量count:0// 获取字符串长度n:len(s)// 循环条件// 1. 左指针不越界l 0// 2. 右指针不越界r n// 3. 左右两边字符相等s[l] s[r]// 满足 → 说明是回文forl0rns[l]s[r]{count// 找到一个回文计数 1l--// 左指针继续向左扩展r// 右指针继续向右扩展}// 返回本次中心扩展找到的回文总数returncount}// countSubstrings 作用统计字符串中所有回文子串的数量funccountSubstrings(sstring)int{// 最终结果所有回文子串的总数res:0n:len(s)// 遍历字符串的每一个位置作为回文的中心fori:0;in;i{// 情况 1奇数长度回文中心是 1 个字符 iresexpand(s,i,i)// 情况 2偶数长度回文中心是 2 个字符 i 和 i1resexpand(s,i,i1)}// 返回最终统计的总数量returnres}funcmain(){// 示例 1输入 abc → 输出 3a、b、cfmt.Println(countSubstrings(abc))// 示例 2输入 aaa → 输出 6fmt.Println(countSubstrings(aaa))}时间复杂度O(n²)外层遍历所有中心O(n)每个中心最多向左右扩展n次O(n)总复杂度n * n n²空间复杂度O(1)只使用了固定几个变量res、left、right、n没有开辟额外的数组/切片和输入长度无关5.最长回文子串题目给你一个字符串 s找到 s 中最长的 回文 子串。示例 1输入s “babad”输出“bab”解释“aba” 同样是符合题意的答案。示例 2输入s “cbbd”输出“bb”提示1 s.length 1000s 仅由数字和英文字母组成思路所有回文串都一定有一个中心点。回文只有两种奇数长度中心点是1 个字符如a、aba、abcba偶数长度中心点是2 个相邻字符如aa、abba、acc a遍历字符串的每一个位置。对每个位置做两种尝试把它当作奇数长度回文中心向左右扩展把它和下一个字符当作偶数长度回文中心向左右扩展每次扩展时只要左右字符相等就是回文。全程记录最长回文的起始位置和长度。最后根据记录截取出最长回文子串返回。代码实现Go:packagemainimportfmt// expand 从 l、r 中心向两边扩展返回【最长回文的长度】funcexpand(sstring,l,rint)int{n:len(s)// 不越界且字符相等就继续扩展forl0rns[l]s[r]{l--r}// 循环结束时最后一次有效回文长度 r - l - 1returnr-l-1}// longestPalindrome 寻找最长回文子串funclongestPalindrome(sstring)string{n:len(s)ifn0{return}// 记录最长回文的起始位置和长度// 最短回文长度是1单个字符start:0maxLength:1// 遍历每个可能的回文中心fori:0;in;i{// 奇数长度回文len1:expand(s,i,i)// 偶数长度回文len2:expand(s,i,i1)// 取两种情况中更长的那个maxLen:max(len1,len2)// 如果当前长度 记录的最长长度则更新ifmaxLenmaxLength{maxLengthmaxLen starti-(maxLen-1)/2}}// 截取并返回最长回文returns[start:startmaxLength]}funcmain(){fmt.Println(longestPalindrome(babad))// 输出 bab / abafmt.Println(longestPalindrome(cbbd))// 输出 bb}时间复杂度O(n²)遍历每个中心 O(n)每个中心最多扩展 O(n)空间复杂度O (1)只使用了几个变量没有开辟额外空间
【Day45】647. 回文子串 5. 最长回文子串
发布时间：2026/5/18 10:43:32
文章目录647.回文子串题目思路代码实现Go5.最长回文子串题目思路代码实现Go:647.回文子串题目给你一个字符串 s 请你统计并返回这个字符串中回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。示例 1输入s “abc”输出3解释三个回文子串: “a”, “b”, “c”示例 2输入s “aaa”输出6解释6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”提示1 s.length 1000s 由小写英文字母组成思路题目要找字符串里所有连续的、正读反读一样的子串数量。回文串一定有中心点只有两种情况奇数长度中心点是 1 个字符如a、aba偶数长度中心点是 2 个相邻字符如aa、abba中心扩展法遍历字符串的每一个位置把它当作奇数回文中心遍历每一对相邻位置把它们当作偶数回文中心从中心往左右两边扩散只要左右字符相等就是一个回文每找到一个回文总数 1代码实现Gopackagemainimportfmt// expand 函数作用// 从给定的左指针 l、右指针 r 开始向左右两边扩展// 统计以 l、r 为中心的回文子串个数funcexpand(sstring,l,rint)int{// 记录本次扩展能找到的回文数量count:0// 获取字符串长度n:len(s)// 循环条件// 1. 左指针不越界l 0// 2. 右指针不越界r n// 3. 左右两边字符相等s[l] s[r]// 满足 → 说明是回文forl0rns[l]s[r]{count// 找到一个回文计数 1l--// 左指针继续向左扩展r// 右指针继续向右扩展}// 返回本次中心扩展找到的回文总数returncount}// countSubstrings 作用统计字符串中所有回文子串的数量funccountSubstrings(sstring)int{// 最终结果所有回文子串的总数res:0n:len(s)// 遍历字符串的每一个位置作为回文的中心fori:0;in;i{// 情况 1奇数长度回文中心是 1 个字符 iresexpand(s,i,i)// 情况 2偶数长度回文中心是 2 个字符 i 和 i1resexpand(s,i,i1)}// 返回最终统计的总数量returnres}funcmain(){// 示例 1输入 abc → 输出 3a、b、cfmt.Println(countSubstrings(abc))// 示例 2输入 aaa → 输出 6fmt.Println(countSubstrings(aaa))}时间复杂度O(n²)外层遍历所有中心O(n)每个中心最多向左右扩展n次O(n)总复杂度n * n n²空间复杂度O(1)只使用了固定几个变量res、left、right、n没有开辟额外的数组/切片和输入长度无关5.最长回文子串题目给你一个字符串 s找到 s 中最长的 回文 子串。示例 1输入s “babad”输出“bab”解释“aba” 同样是符合题意的答案。示例 2输入s “cbbd”输出“bb”提示1 s.length 1000s 仅由数字和英文字母组成思路所有回文串都一定有一个中心点。回文只有两种奇数长度中心点是1 个字符如a、aba、abcba偶数长度中心点是2 个相邻字符如aa、abba、acc a遍历字符串的每一个位置。对每个位置做两种尝试把它当作奇数长度回文中心向左右扩展把它和下一个字符当作偶数长度回文中心向左右扩展每次扩展时只要左右字符相等就是回文。全程记录最长回文的起始位置和长度。最后根据记录截取出最长回文子串返回。代码实现Go:packagemainimportfmt// expand 从 l、r 中心向两边扩展返回【最长回文的长度】funcexpand(sstring,l,rint)int{n:len(s)// 不越界且字符相等就继续扩展forl0rns[l]s[r]{l--r}// 循环结束时最后一次有效回文长度 r - l - 1returnr-l-1}// longestPalindrome 寻找最长回文子串funclongestPalindrome(sstring)string{n:len(s)ifn0{return}// 记录最长回文的起始位置和长度// 最短回文长度是1单个字符start:0maxLength:1// 遍历每个可能的回文中心fori:0;in;i{// 奇数长度回文len1:expand(s,i,i)// 偶数长度回文len2:expand(s,i,i1)// 取两种情况中更长的那个maxLen:max(len1,len2)// 如果当前长度 记录的最长长度则更新ifmaxLenmaxLength{maxLengthmaxLen starti-(maxLen-1)/2}}// 截取并返回最长回文returns[start:startmaxLength]}funcmain(){fmt.Println(longestPalindrome(babad))// 输出 bab / abafmt.Println(longestPalindrome(cbbd))// 输出 bb}时间复杂度O(n²)遍历每个中心 O(n)每个中心最多扩展 O(n)空间复杂度O (1)只使用了几个变量没有开辟额外空间
