5. Longest Palindromic Substring

题目 #

Given a string s, return the longest palindromic substring in s.

思路1 #

  • 暴力破解,遍历所有子串,判断是否为回文串
  • 时间复杂度 $O(n^2)$

思路2 #

  • 用i表示中心点,向两边扩展判断最长的回文串
  • 顺便判断一下i作为中心线前一个的情况
  • 时间复杂度 $O(n^2)$
 1func longestPalindrome(s string) (result string) {
 2	for i := range s {
 3		// think medium of palindrome as i
 4		left := i - 1
 5		right := i + 1
 6		for left >= 0 && right < len(s) {
 7			if s[left] != s[right] {
 8				break
 9			}
10			left--
11			right++
12		}
13		left++
14		if right-left > len(result) {
15			result = s[left:right]
16		}
17		// think medium of palindrome as i and i+1
18		left = i
19		right = i + 1
20		for left >= 0 && right < len(s) {
21			if s[left] != s[right] {
22				break
23			}
24			left--
25			right++
26		}
27		left++
28		if right-left > len(result) {
29			result = s[left:right]
30		}
31	}
32	return
33}

思路3 #

  • Manache算法,可以将时间复杂度降低到 $O(n)$
  • 不过稍微有点不好理解
  • 就是在思路2的基础上,按照前面某个回文串(要求i在其臂长内)的中心进行对称一下,对称点已经有结果就可以少判断已经判断的地方
 1func longestPalindrome(s string) string {
 2	start, end := 0, -1
 3	t := "#"
 4	for i := 0; i < len(s); i++ {
 5		t += string(s[i]) + "#"
 6	}
 7	t += "#"
 8	s = t
 9	arm_len := []int{}
10	right, j := -1, -1
11	for i := 0; i < len(s); i++ {
12		var cur_arm_len int
13		if right >= i {
14			i_sym := j*2 - i
15			min_arm_len := min(arm_len[i_sym], right-i)
16			cur_arm_len = expand(s, i-min_arm_len, i+min_arm_len)
17		} else {
18			cur_arm_len = expand(s, i, i)
19		}
20		arm_len = append(arm_len, cur_arm_len)
21		if i+cur_arm_len > right {
22			j = i
23			right = i + cur_arm_len
24		}
25		if cur_arm_len*2+1 > end-start {
26			start = i - cur_arm_len
27			end = i + cur_arm_len
28		}
29	}
30	ans := ""
31	for i := start; i <= end; i++ {
32		if s[i] != '#' {
33			ans += string(s[i])
34		}
35	}
36	return ans
37}
38
39func expand(s string, left, right int) int {
40	for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {
41	}
42	return (right - left - 2) / 2
43}
44
45func min(x, y int) int {
46	if x < y {
47		return x
48	}
49	return y
50}