leetcode day3

发表于 | 更新于

此题来自LeetCode,系中等难度的算法题

题目

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

示例 1：

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

示例 2：

输入: "cbbd"
输出: "bb"

解答

这道题我原本想像之前一样使用滑动窗口做的,但后来发现回文子串不能像之前那样的判断机制,遂还是采用了暴力法(:з」∠)

暴力法

暴力法遍历所有子串需要O(n^2)的时间,验证是否是回文需要O(n)的时间,所以时间复杂度是O(n^3)

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 {
	sLen := len(s)
	var res string
	for i := 0; i < sLen; i++ {
		for j := i + 1; j <= sLen; j++ {
			if isPalindrome(s[i:j]) {
				if len(res) < j-i {
					res = s[i:j]
				}
			}
		}
	}
	return res
}

//判断一个字符串是否是回文
func isPalindrome(s string) bool {
	sLen := len(s)
	if sLen == 0 {
		return true
	}
	for i := 0; i < sLen/2; i++ {
		if s[i] != s[sLen-i-1] {
			return false
		}
	}
	return true
}

中心扩展算法

中心扩展算法以一个的字符串的每个字符为中心点,如果其左右字符一样的话,那么该字符串就是回文.例如”a”字符,如果左右字符均为”b”,即”bab”也是回文,以此类推…

值得注意的是:字符数为奇数的回文和字符数为偶数的回文需要分情况讨论.因为”aba”的中心字符是”b”,而”abba”的中心字符是”bb”

中心扩展算法的时间复杂度为O(n^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
func longestPalindrome(s string) string {
	var start, end int
	for i := 0; i < len(s); i++ {
		left1, right1 := expendAroundCenter(s, i, i)
		left2, right2 := expendAroundCenter(s, i, i+1)
		if right2-left2 > right1-left1 {
			if end-start < right2-left2 {
				start = left2
				end = right2
			}
		} else {
			if end-start < right1-left1 {
				start = left1
				end = right1
			}
		}

	}
	return s[start:end+1]
}

func expendAroundCenter(s string, left, right int) (rleft, rright int) {
	rleft, rright = left, right
	for rleft >= 0 && rright < len(s) && s[rleft] == s[rright] {
		rleft -= 1
		rright += 1
    }
    rleft+=1
    rright-=1
	return
}

小结

最长回文子串的解决算法有多种,我仅仅是使用了最简单的暴力法以及借鉴了解答思路中的中心扩展法.除此之外,还有Manacher算法和最长公共子串法值得参考

0%