5. 最长回文子串

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

解法一、动态规划

主要就是状态转移方程的确定。
确定回文串的左右索引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)，即存储动态规划状态需要的空间。

    1. //动规，时空都为On^2
    2. func longestPalindrome(s string) string {
    3.   n := len(s)
    4.   dp := make([][]bool, n)
    6.   max := 1            // 最大长度 
    7.   begin := 0          // 起始索引
    9.   if n <= 1 {         // 特别判断，单字符或空字符串，就是其自身
    10.       return s
    11.   }
    13.   for k := range dp {
    14.       dp[k] = make([]bool, n)
    15.       dp[k][k] = true
    16.   }
    18.   for left := l - 1; left >= 0; left-- {                //一个倒序，一个正序，正序在倒序之后
    19.       for right := left + 1; right < l; right++ {
    20.           if s[left] != s[right] {
    21.               dp[left][right] = false
    22.               continue
    23.           }
    24.           if right - left <= 2 {
    25.               dp[left][right] = true
    26.           } else {
    27.               dp[left][right] = dp[left+1][right-1]
    28.           }
    30.           if dp[left][right] == true && right - left + 1 > max {
    31.               max = right - left + 1
    32.               begin = left
    33.           }
    34.       }
    35.   }
    36.   return s[begin: begin + max]
    37. }

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

解题思路

回文分两种:

  • 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，空间O1
func longestPalindrome(s string) string {
    if len(s) == 0 {
        return ""
    }

    left, right := 0, 0
    for k := range s {
        l1, l2 := expand(s, k, k), expand(s, k, k+1)    //奇偶两种？
        l := int(math.Max(float64(l1), float64(l2)))

        if l > right-left {
            left = k - (l-1)/2                //没看懂？ 7-1 / 2 = 3
            right = k + l/2                    // 7/2 = 3 +k = 4?
        }
    }
    return s[left : right+1]
}

// 向轴两边对称，找最大回文串
func expand(s string, left, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    return right - left - 1
}

中心扩散法怎么去找回文串？
从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。

举个例子，str = acdbbdaastr=acdbbdaa 我们需要寻找从第一个 b（位置为 33）出发最长回文串为多少。怎么寻找？
首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
最后左右双向扩散，直到左和右不相等。如下图所示：

//中心拓展法
func longestPalindrome(s string) string {
    start, end := 0, 0
    for i := range s {
        l, r := expand(s, i, i)     // 奇数的情况 
        if end - start < r - l {    // 如果有更大的边界值
            start, end = l, r
        }

        l, r = expand(s, i, i+1)    // 偶数的情况
        if end - start < r - l {    // 如果有更大的边界值
            start, end = l, r
        }
    }
    return s[start:end+1]
}

// 围绕中心展开
func expand(s string, left, right int) (int, int) {
    for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left - 1, right + 1 {
    }
    return left + 1, right - 1; // 上面的循环最后那块把多操作的加减回去
}