给你一个字符串 s，找到 s 中最长的回文子串。

示例 1:

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2:

输入：s = "cbbd"
输出："bb"

说明:

1 <= s.length <= 1000
s 仅由数字和英文字母组成

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

// 暴力法
func longestPalindrome(s string) string {
	var left, right, length int
	for i := 0; i <= len(s)-1; i++ {
		for j := i + 1; j <= len(s)-1; j++ {
			if s[i] != s[j] {
				continue
			}
			isPalindrome := checkIsPalindrome(s, i, j)
			// 记录初始值与长度
			if isPalindrome && (j-i+1) > length {
				left = i
				right = j
				length = j-i+1
			}
		}
	}
	return string([]byte(s)[left:right+1])
}

func checkIsPalindrome(s string, start int, end int) bool {
	for start < end {
		if s[start] != s[end] {
			return false
		}
		start++
		end--
	}
	return true
}

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

// 中心扩展
func longestPalindrome(s string) string {
	var max, start, end int
	for i := 0; i < len(s); i ++ {
		left, right := expandFromCenter(s, i, i)
		if max < right - left + 1 {
			max = right - left + 1
			start, end = left, right
		}
		left, right = expandFromCenter(s, i, i + 1)
		if max < right - left + 1 {
			max = right - left + 1
			start, end = left, right
		}
	}
	return s[start:end + 1]
}

func expandFromCenter(s string ,left, right int)(int, int){
	for left >= 0 && left <= right && right < len(s) {
		if s[left] != s[right] {
			break
		}
		left--
		right++
	}
	return left + 1, right - 1
}

3.动态规划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func longestPalindrome(s string) string {
	// 方程式
	// dp[1][2] = dp[2][1]
	// dp[1][3] = dp[2][2]
	// dp[1][4] = dp[2][3]
	// dp[i][j] = dp[i+1]dp[j-1] && s[i] = s[j]
	ans := ""
	dp := make([][]bool, len(s))
	for k, _ := range s {
		dp[k] = make([]bool, len(s))
	}
	for i := 0; i < len(s); i++ {
		for k := 0; k <= i; k++ {
			// 相邻两个相等或本身就同一个
			dp[i][k] = ((i-k <= 1) || dp[i-1][k+1]) && s[i] == s[k]
			if dp[i][k] && (i-k+1) > len(ans) {
				ans = s[k : i+1]
			}
		}
	}
	return ans
}