发布于 

最长回文子串

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

题目大意

根据回文子串的定义，枚举所有长度大于等于 2 的子串，依次判断它们是否是回文。在具体实现时，可以只针对大于 “当前得到的最长回文子串长度” 的子串进行 “回文验证”，例如以上例子中的aba、bab，而abc显然不是。

解题思路&代码

方法一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func longestPalindrome(s string) string {
    var strLen, maxLen int = len([]rune(s)), 1
    if strLen < 2 {
        return s
    }
    
    var resStr = s[:1]
    // 枚举所有长度>=2的子串
    for i := 0; i < strLen - 1; i++ {
        for j := i + 1; j < strLen; j++ {
            if j - i + 1 > maxLen && isValid(s, i, j) {
                maxLen = j - i + 1
                resStr = s[i:j + 1]
            }
        }
    }
    return resStr
}

func isValid(s string, left, right int) bool {
    for left < right {
        if (s[left] != s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}

复杂度分析

  • 时间复杂度：O(n3)O(n^3)，两层 for 循环 O(n2)O(n^2)，for 循环里边判断是否为回文 O(n)O(n)，所以时间复杂度为 O(n3)O(n^3)
  • 空间复杂度：O(1)O(1)，只使用到常数个临时变量，与字符串长度无关。

考虑使用双指针和滑动窗口解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func longestPalindrome(s string) string {
	  if len(s) < 2 {
        return s
    }
    longest := s[0:1]
    for i := 1; i < len(s); i++ {
        // Step为2
        for rightStep := 0; rightStep < 2; rightStep++ {
            // 索引位置两侧元素必须相等
            for p, q := i-1, i+rightStep; p >= 0 && q < len(s) && s[p] == s[q]; {
                if q-p+1 > len(longest) {
                    longest = s[p : q+1]
                }
               // 由i位置开始向两侧扩散 
                p--
                q++
            }
        }
    }
    return longest
}

方法二：中心扩散

暴力法是采用双指针两边扫描，验证是否是回文子串，时间复杂度比较高。另一种思路是枚举可能出现的回文子串的 “中心位置”，从 “中心位置” 尝试尽可能扩散出去，得到一个回文子串。

因此，中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用 “回文串” 中心对称的特点，往两边扩散，直到无重复子串为止。

枚举 “中心位置” 时间复杂度为 O(n)O(n)，从 “中心位置” 扩散得到 “回文子串” 的时间复杂度为 O(n)O(n)，因此时间复杂度可以降到 O(n2)O(n^2)。

在这里要关注一个细节：回文串在长度为奇数和偶数的时候，”回文中心” 的形式是不一样的。

  • 奇数回文串的 “中心” 是一个具体的字符，例如：回文串 "aba" 的中心是字符 "a"；
  • 偶数回文串的 “中心” 是位于中间的两个字符的 “空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间。

palindromic_1

所有可能的回文串位置如下：

palindromic_2

  • 如果回文串中心为索引编码，向外围扩散，则得到的回文串的长度为奇数
  • 如果回文串中心为相邻的索引编码，向外围扩散，则得到的回文串的长度为偶数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func longestPalindrome(s string) string {
    var strLen, maxLen int = len([]rune(s)), 1
    if strLen < 2 {
        return s
    }
    
    var resStr string = s[:1]
    // 枚举所有长度>=2的子串
    for i := 0; i < strLen - 1; i++ {
        var oddStr, evenStr, maxLenStr = centerSpread(s, i, i),centerSpread(s, i, i+1), ""
        if len([]rune(oddStr)) > len([]rune(evenStr)) {
            maxLenStr = oddStr
        } else {
            maxLenStr = evenStr
        }
        if (len([]rune(maxLenStr)) > maxLen) {
            maxLen = len([]rune(maxLenStr))
            resStr = maxLenStr
        }
        
    }
    return resStr
}

func centerSpread(s string, left, right int) string {
    // left = right 的时候, 此时回文中心是一个空隙, 回文串的长度是奇数
    // right = left + 1 的时候, 此时回文中心是任意一个字符, 回文串的长度是偶数
    var strLen = len([]rune(s))
    for left >= 0 && right < strLen {
        if (s[left] == s[right]) {
            left--
            right++
        } else {
            break
        }
    }
    return s[left+1: right]
}

复杂度分析

  • 时间复杂度：O(n2)O(n^{2})，理由已经叙述。
  • 空间复杂度：O(1)O(1)，只使用到常数个临时变量，与字符串长度无关。

方法三：Manacher 算法

在方法二中时间复杂度O(n2)O(n^{2})，对于较长的字符串是难以接受的。

方法二存在的缺陷：

缺陷1

  • 由于回文串长度的奇偶性造成了不同性质的对称轴位置，方法2要对两种情况分别处理；
  • 很多子串被重复多次访问，造成较差的时间效率。

缺陷2

可以通过这个直观体现：

charababa
i01234

当i==1，和i==2时，左边的子串aba分别被遍历了一次。

以下使用 Manacher （马拉车）算法解决上述问题：

解决长度奇偶性带来的对称轴位置问题

Manacher 算法首先对字符串做一个预处理，在所有的空隙位置(包括首尾)插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入*号为例：

1
2
aba  --->  *a*b*a*
abba --->  *a*b*b*a*

插入的是同样的符号，且符号不存在于原串，因此子串的回文性不受影响。 原来是回文的串，插完之后还是回文的，原来不是回文的，不受影响。

这一处与寻找两个有序数组的中位数中使用的方式类似

解决重复遍历的问题

把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher 算法中定义了一个回文半径数组RL，用 RL[i] 表示以第 i 个字符为对称轴的回文串的回文半径。对字符串从左往右处理，因此这里定义 RL[i]为第 i 个字符为对称轴的回文串的最右一个字符与字符 i 的距离。对于上面插入分隔符之后的两个串，可以得到 RL数组：

char*a*b*a*
i0123456
RL1214121
RL-10103010
char*a*b*b*a*
i012345678
RL121252121
RL-1010141010

观察可以发现，RL[i]-1的值，正是在原本那个没有插入过分隔符的子串中，以位置 i 为对称轴的最长回文串的长度。那么只要我们求出了RL数组，就能得到最长回文子串的长度。

基本思路是利用回文串的对称性，扩展回文串。

首先从左往右依次计算 Len[i]，当计算 Len[i]时，Len[j](0<=j<i)已经计算完毕。设 P 为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为 Po，分两种情况：

第一种情况：i<=P

那么找到 i 相对于P0的对称位置，设为 j，那么如果 Len[j]<P-i，如下图：

palindromic_3

以 j 为中心的回文串一定在以 Po 为中心的回文串的内部，且 j 和 i 关于位置 Po 对称，由回文串的定义可知，一个回文串反过来还是一个回文串，所以以 i 为中心的回文串的长度至少和以 j 为中心的回文串一样，即Len[i]>=Len[j]。因为Len[j]<P-i,所以说i+Len[j]<P。由对称性可知Len[i]=Len[j]。

如果 Len[j]>=P-i,由对称性，说明以 i 为中心的回文串可能会延伸到 P 之外，而大于 P 的部分我们还没有进行检索，所以要从 P+1 位置开始逐一进行匹配，直到发生失配，更新 P 和对应的 Po 以及 Len[i]。

palindromic_4

第二种情况: i>P

如果i比P还要大，说明对于中点为i的回文串还没有匹配到，逐一匹配后更新P的位置和对应的Po以及Len[i]。

复杂度分析

  • 时间复杂度：O(n)O(n)，这里 n 是原始字符串的长度。新字符串的长度是 2n+12n+1，不计系数与常数项，因此时间复杂度仍为 O(N2)O(N^2)。
  • 空间复杂度：O(n)O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func longestPalindrome(s string) string {
    var strLen, maxLen int = len([]rune(s)), 1
    if strLen < 2 {
        return s
    }
    var strNew string = addBoundaries(s, '*')
    var start int
    var lenNew = 2 * strLen + 1
    for i := 0; i < lenNew; i++ {
        var curLen = centerSpread(strNew, i)
        if curLen > maxLen {
            maxLen = curLen
            start = (i - maxLen) / 2
        }
    }
    return s[start: start + maxLen]
}

func centerSpread(s string, center int) int {
    var strLen = len([]rune(s))
    var i, j, step = center - 1, center + 1, 0
    for i >= 0 && j < strLen && s[i] == s[j] {
        i--
        j++
        step++
    }
    return step
}

// 处理字串 "*a*b*a*"
func addBoundaries(s string, divide byte) string {
    var strLen = len([]rune(s))
    if (strLen == 0) {
        return ""
    }
    if (strings.IndexByte(s, divide) != -1) {
        panic("divide char is exist in `s`")
    }
    var buf bytes.Buffer
    var i int
    for i = 0; i < strLen; i++ {
        buf.WriteByte(divide)
        buf.WriteByte(s[i])
    }
    buf.WriteByte(divide)
    return buf.String()
}

方法四：动态规划

1、定义 “状态”；
2、找到 “状态转移方程”。

下文中，使用记号 S[l, r] 表示原始字符串的一个子串，l、r 分别是区间的左右边界的索引值，如 S 为 ‘ababa’ 时，S[0, 1] = ‘ab’ ，S[2, 4] = ‘aba’。

定义 “状态”

dpl,rdp_{l,r}表示子串 `S[l, r]`是否构成回文串

找到 “状态转移方程”

首先，我们很清楚一个事实：

  • 1、当子串只包含 1 个字符，那么它一定是回文子串；

  • 2、当子串包含 2 个以上字符的时候：如果 S[l, r] 是一个回文串，例如 “ababa”，那么 S[l + 1, r - 1] 也一定是回文串，即 dpl+1,r−1=truedp_{l+1,r-1} = true

定义 dpl,rdp_{l,r}。

dpl,r={trueS[l,r]是回文串falseS[l,r]不是回文串dp_{l,r}=\begin{cases}true& \text{S[l,r]是回文串}\\\\false& \text{S[l,r]不是回文串}\end{cases}

所以如果 S[l] != S[r]，那么这个子串就一定不是回文串。如果 S[l] == S[r] 成立，就接着判断 S[l + 1] 与 S[r - 1]。

总结以上，只要 S[l + 1, r - 1] 至少包含两个元素，就继续做判断，否则直接根据左右边界是否相等就能得到原字符串的回文性。如果一个字符串的左右边界相等，以下二者之一成立即可：

  • 1、去掉左右边界以后的字符串不构成区间，即”S[l + 1, r - 1] 至少包含两个元素”的反面，即 l - r >= -2，或者 r - l <= 2；
  • 2、去掉左右边界以后的字符串是回文串。

于是如下”状态转移方程”成立：

dpl,r=S[l]==S[r]∧(l−r>=−2∨dpl+1,r−1)dp_{l,r} = S[l] == S[r] ∧ (l - r >= -2 ∨ dp_{l + 1, r - 1})

或者

dpl,r=S[l]==S[r]∧(r−l<=2∨dpl+1,r−1)dp_{l,r} = S[l] == S[r] ∧ (r - l <= 2 ∨ dp_{l + 1, r - 1})
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章
快来参与讨论吧