5. 最长回文子串 难呀

给你一个字符串 s，找到 s 中最长的回文子串。连续
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

  1. //双指针 中心拓展算法，时间On^2，空间O1
  2. func longestPalindrome(s string) string {
  3.     if len(s) == 0 {
  4.         return ""
  5.     }
  7.     left, right := 0, 0
  8.     for k := range s {
  9.         l1, l2 := expandLength(s, k, k), expandLength(s, k, k+1)
  10.         l := int(math.Max(float64(l1), float64(l2)))
  12.         if l > right-left {
  13.             left = k - (l-1)/2                //没看懂？ 7-1 / 2 = 3
  14.             right = k + l/2                    // 7/2 = 3 +k = 4?
  15.         }
  16.     }
  17.     return s[left : right+1]
  18. }
  20. // 向轴两边对称，找最大回文串
  21. func expandLength(s string, left, right int) int {
  22.     for left >= 0 && right < len(s) && s[left] == s[right] {
  23.         left--
  24.         right++
  25.     }
  26.     return right - left - 1
  27. }

解法二、中心拓展-轴对称

解题思路

回文分两种:

  • 1、奇数个字符，比如“aba”，b像一根轴，让两边的a保持对称
  • 2、偶数个字符，比如“abba”，“ab”和“ba”对称

所以，思路就是遍历每个字符，做两次对称判断：

  • 1、以自身为轴，向两边扩展，如果两边扩展项总是一致，就一直拓展，否则，就结束。类似：

    thing a gnithsd
<---- a ---->

  • 2、以自身和下个字符结合体为轴，执行和上面类似的判断。当然，这是有条件的，就是下个字符要和自身相同

    thing aa gnithsd
<---- aa ---->

中心点一共有多少个呢？看起来像是和字符串长度相等，但你会发现，如果是这样，上面的例子永远也搜不到 abab，想象一下单个字符的哪个中心点扩展可以得到这个子串？似乎不可能。所以中心点不能只有单个字符构成，还要包括两个字符，比如上面这个子串 abab，就可以有中心点 ba 扩展一次得到，所以最终的中心点由 2 * len - 1 个，分别是 len 个单字符和 len - 1 个双字符。
如果上面看不太懂的话，还可以看看下面几个问题：

  • 为什么有 2 * len - 1 个中心点？
    • aba 有5个中心点，分别是 a、b、c、ab、ba
    • abba 有7个中心点，分别是 a、b、b、a、ab、bb、ba
  • 什么是中心点？
    • 中心点即 left 指针和 right 指针初始化指向的地方，可能是一个也可能是两个
  • 为什么不可能是三个或者更多？
    • 因为 3 个可以由 1 个扩展一次得到，4 个可以由两个扩展一次得到

时间复杂度：O(n^2)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n-1 个，每个回文中心最多会向外扩展 O(n) 次。
空间复杂度：O(1)。 

//动规，时空都为On^2
func longestPalindrome(s string) string {
    n := len(s)
    dp := make([][]bool, n)

    max := 1            // 最大长度 
    begin := 0          // 起始索引

    if n <= 1 {         // 特别判断，单字符或空字符串，就是其自身
        return s
    }

    for k := range dp {
        dp[k] = make([]bool, n)
        dp[k][k] = true
    }

    for left := l - 1; left >= 0; left-- {                //一个倒序，一个正序，正序在倒序之后
        for right := left + 1; right < l; right++ {
            if s[left] != s[right] {
                dp[left][right] = false
                continue
            }
            if right - left <= 2 {
                dp[left][right] = true
            } else {
                dp[left][right] = dp[left+1][right-1]
            }

            if dp[left][right] == true && right - left + 1 > max {
                max = right - left + 1
                begin = left
            }
        }
    }
    return s[begin: begin + max]
}

解法一、动态规划

主要就是状态转移方程的确定。
确定回文串的左右索引left/right， 备忘录为memo，其中memo[left][right]表示从s截取left到right后是回文串吗？

  • 1、如果s[left]!=s[right]，那么memo[left][right]为false
  • 2、如果s[left]==s[right]
    • 1）如果左右指针之间差距小于等于2，那铁定是回文串
  • aa和a，肯定是回文串对不对
    • 2）如果左右指针之间差距大于2，那就看s[left][right]其子串是不是回文串了，即s[left+1][right-1]
  • bac不是回文串了，dbacd肯定也不是

  • 3、每当memo[left][right]为true的时候，就看看left到right构成的子串是不是当前最长的。 是的话，把它起始位置和长度记下来，方便最后截取。

  • 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。

  • 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。