Golang算法之无最长的回文子串

最长回文子串，中等难度，leetcode地址：https://leetcode-cn.com/problems/longest-palindromic-substring

1.描述

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

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

2.题解

首先，得理解什么叫回文，回就是来回的回，所谓回文就是从两边来回读都一样，比如121、aba、上海自来水来自海上。。。

这么一说大家应该都理解了，但是此题需要找的是一个字符串里面最长的回文子串，有3个限定条件：子串、回文、最长。

方法一:

最简单的就是暴力循环法，我们只需要找出所有子串，然后判断其是否是回文，然后再更新最大长度，代码逻辑简单易懂，朴实无华。

参考代码：

func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    max := 0
    longestStr := ""
    for i := 0; i < len(s); i++ {
        for j := i + 1; j <= len(s); j++ {
            str := s[i:j]
            if len(str) <= max {
                continue
            }
            if isPalindrome(str) {
                max = len(str)
                longestStr = str
            }
        }
    }
    return longestStr
}

// 判断是否是回文
func isPalindrome(s string) bool {
    n := len(s)
    for i := 0; i < n/2; i++ {
        if s[i] != s[n-i-1] {
            return false
        }
    }
    return true
}

然而，这种方式过于简单，而且时间复杂度高，N3，肯定不是题目考察的重点，所以下面还有更高级的解法。

方法二:

中心扩散法，因为回文串满足分2种，一种是长度奇数，比如 “aba”，另一种是长度为偶数的，比如 “abba”，我们可以遍历字符串，对取得每一个字符都假设其可能成为最后的中心进行扩散，判断有没有回文存在。

以字符串”121a1bc”为例:

假设第3个字符1是回文的中心，那么2应该等于a，很明显不满足回文的的条件

假设1a是回文中心，那么1应该等于a，2应该等于b，很明显也不是

假设第4个字符a是回文中心，那么1应该等于1，满足条件，这时候继续往两边扩散，判断2是不是等于b，很明显不满足条件

参考代码:

func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    ls := ""
    for i := 0; i < len(s); i++ {
        ls = isPalindrome(s, ls, i, i)
        ls = isPalindrome(s, ls, i, i+1)
    }
    return ls
}

func isPalindrome(s, ls string, i, j int) string {
    for {
        // 从当前位置往2边扩散，直到不满足回文的条件，注意临界条件
        if i >= 0 && j < len(s) && s[i] == s[j] {
            i--
            j++
        } else {
            break
        }
    }
    if j-i-1 > len(ls) {
        ls = s[i+1 : j] //Go的slice截取含头不含尾
    }
    return ls
}

此种解法时间复杂度N2，效率很高，leetcode里面执行4ms，击败96%的用户，而前面的暴力循环法则需要160ms。