最长回文子串

题目

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-palindromic-substring

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
1
2
3

示例 2:

输入: "cbbd"
输出: "bb"
1
2

回文

回文,palindromic,是一个正读和反读都相同的字符串,例如aba 是回文,而 abc 不是。也就是 s[i-n:i] == reverse[i+1:i+n+1]

中心扩展算法

方案

中心扩展的意思,就是选定好回文串的中心,然后向两侧扩展比较。

中心的确定需要注意,某个字符可以为中心,同样两个字符的间隔也可以为中心,因此若长度为 n,则会存在 2*n-1 个中心。可以想象为:a#b#c ,中心在字符或 # 上。

编码时,外层循环确定中心,内层循环进行两侧字符比较。由于中心可能在字符或间隔(#)上,因此计算两侧字符索引的方法有些差异,要注意!

Go 实现

该实现在 Leetcode 上通过,表现如下:

执行用时 :4 ms, 在所有 golang 提交中击败了94.32%的用户

内存消耗 :2.2 MB, 在所有 golang 提交中击败了80.85%的用户

func longestPalindrome(s string) string {
	// 长度
	l := len(s)
	// 空字符串特例
	if l == 0 {
		return s
	}
	// 当前回文串的起止索引
	b,e:=0,0 // 当前回文串
	// 遍历全部的中心
	// l 个字符,就有 2*l - 1 个中心,因为 aba 或 abba 都是回文数,意味着两个字符间也可为中心。可假设 a#b#c#d, 可以想象成以#插入
	for i,last := 0, 2*l-1; i<last; i++ {
		// 0: -1, 1  i/2-1, i/2+1
		// 1: 0, 1	(i+1)/2-1, (i+1)/2
		// 2: 0, 2  i/2-1, i/2+1
		// 3: 1, 2 (i+1)/2-1, (i+1)/2
		// 计算中心两侧的元素索引,
		// 因为中心可能在字符上,也可能在字符间,因此需要利用 %2 进行计算,上面是例子,下面的计算方案
		m := i%2
		p, ne := (i+m)/2-1, (i+m)/2+1-m
		// 从中心两侧开始比较,相等则继续比较,不相等,查看当前回文串的长度是否比之前发现的长
		for n:=1; p>=0 && ne < l && s[p] == s[ne]; n, p, ne = n+1, p-1, ne+1 {
			// 越界 或 碰到不等的字符
			// 比较长度,记录
			if 2*n+1 > e-b+1 {
				b, e = p, ne
			}
		}
		// 若 遍历到一半,发现回文串的长度已经大于一半了,表示不会再有更长的回文串了,稍微优化下
		if e-b +1 > l /2 && i > l {
			break
		}
	}
	// 返回回文串
	return string(s[b:e+1])
}
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

该算法的时间复杂度为 O(n^2)。双重循环的遍历,典型的 n^2 复杂度。

还有一种算法 Manacher 可达到 O(n) 的时间复杂度,继续...

Manacher 算法

方案