最长回文子串 | HELLO梧席

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：”bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

func longestPalindrome(s string) string {
    maxstr := ""
    // 遍历字符串s的每一个元素，向该元素左右两侧遍历，判断是否为回文，并记录长度
    // 奇数情况
    for i := 0;i < len(s);i++{
        pr,re := i-1,i+1
        str := string(s[i])
        for pr >= 0 && re < len(s) && s[pr] == s[re]{
            str = string(s[pr]) + str + string(s[re])
            pr--
            re++
        }
        if len(str) > len(maxstr){
            maxstr = str
        }

        // 偶数情况
        if(i+1 < len(s) && s[i]==s[i+1]){
            pr,re := i,i+1
            str := string(s[pr]) + string(s[re])
            for pr >= 0 && re < len(s) && s[pr] == s[re]{
                if pr != i{
                    str = string(s[pr]) + str + string(s[re])
                }
                pr--
                re++
            }
            if len(str) > len(maxstr){
                maxstr = str
            } 
        }   
    }
    return maxstr
}

思路：中心扩散法，类似于双指针遍历，不过是反向的。特别的，这里要考虑两种情况：回文串为奇数的时候以及回文串为偶数的时候。

解题思路

题目要求寻找字符串中的最长回文。当然，我们可以使用下面的程序判断字符串s[i:j+1]是否是回文。

func isPalindromic(s *string, i, j int ) bool {
    for  i< j {
        if (*s)[i] != (*s)[j] {
            return false
        } 
        i++
        j--
    }
    return true
}

但是，这样就没有利用回文的一下特点，假定回文的长度为l，x为任意字符

当l为奇数时，回文的正中间段只会是，“x”，或“xxx”，或“xxxxx”，或…
当l为偶数时，回文的正中间段只会是，“xx”，或“xxxx”，或“xxxxxx”，或…
同一个字符串的任意两个回文substring的正中间段，不会重叠。

题解

func longestPalindrome(s string) string {
	if len(s) < 2 { // 肯定是回文，直接返回
		return s
	}

	// 最长回文的首字符索引，和最长回文的长度
	begin, maxLen := 0, 1

	// 在 for 循环中
	// b 代表回文的**首**字符索引号，
	// e 代表回文的**尾**字符索引号，
	// i 代表回文`正中间段`首字符的索引号
	// 在每一次for循环中
	// 先从i开始，利用`正中间段`所有字符相同的特性，让b，e分别指向`正中间段`的首尾
	// 再从`正中间段`向两边扩张，让b，e分别指向此`正中间段`为中心的最长回文的首尾
	for i := 0; i < len(s); { // 以s[i]为`正中间段`首字符开始寻找最长回文。
		if len(s)-i <= maxLen/2 {
			// 因为i是回文`正中间段`首字符的索引号
			// 假设此时能找到的最长回文的长度为l, 则，l <= (len(s)-i)*2 - 1
			// 如果，len(s)-i <= maxLen/2 成立
			// 则，l <= maxLen - 1
			// 则，l < maxLen
			// 所以，无需再找下去了。
			break
		}

		b, e := i, i
		for e < len(s)-1 && s[e+1] == s[e] {
			e++
			// 循环结束后，s[b:e+1]是一串相同的字符串
		}

		// 下一个回文的`正中间段`的首字符只会是s[e+1]
		// 为下一次循环做准备
		i = e + 1

		for e < len(s)-1 && b > 0 && s[e+1] == s[b-1] {
			e++
			b--
			// 循环结束后，s[b:e+1]是这次能找到的最长回文。
		}

		newLen := e + 1 - b
		// 创新记录的话，就更新记录
		if newLen > maxLen {
			begin = b
			maxLen = newLen
		}
	}

	return s[begin : begin+maxLen]
}

题解中很巧妙的运用了这样一段代码

for e < len(s)-1 && s[e+1] == s[e] {
    e++
    // 循环结束后，s[b:e+1]是一串相同的字符串
}

从而使对于回文数奇偶的处理统一起来。

我的答案中通过记录字符串来进行比较和返回，题解则通过记录回文数的头下标及回文数的最长长度来进行比较和返回，使执行用时和内存消耗都小了很多。

总结

熟悉中心扩散法