golang力扣leetcode 5.最长回文子串

5.最长回文子串 题解

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

思路：

1. 暴力，两重循环，第一层循环i作为起始，第二层循环j作为结束，判断字符串i到j是否是回文串
2. 中心扩散，遍历字符串，以中心作为回文串中心，判断中心的两边，进行扩散
3. dp，dp[i][j]为以i开始j结尾的字符串，如果s[i]==s[j]，那么dp[i][j]=dp[i+1][j-1]，这就是状态转移了，首先要枚举字串长度，再枚举左边界，如果反过来则有些状态是还没有确定的
4. 马拉车算法，O(n)的复杂度，不搞竞赛学这个没什么意义，不写了

代码

//暴力
func longestPalindrome(s string) string {
	n := len(s)
	maxLen := 0
	ans := ""
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			if check(i, j, s) {
				if j-i+1 > maxLen {
					maxLen = j - i + 1
					ans = s[i : j+1]
				}
			}
		}
	}
	return ans
}
func check(l, r int, s string) bool {
	for ; l <= r; l, r = l+1, r-1 {
		if s[l] != s[r] {
			return false
		}
	}
	return true
}

//中心扩散
func longestPalindrome(s string) string {
	n := len(s)
	maxLen := 0
	ans := ""
	for i := 0; i < n; i++ {
		if cnt, ok := check1(i, s); ok {
			if cnt > maxLen {
				maxLen = cnt
				ans = s[i-(cnt-1)/2 : i+(cnt-1)/2+1]
			}
		}
		if cnt, ok := check2(i, i+1, s); ok {
			if cnt > maxLen {
				maxLen = cnt
				ans = s[i-(cnt-1)/2 : i+(cnt-1)/2+2]
			}
		}
	}
	return ans
}
func check1(l int, s string) (int, bool) {
	long := 0
	for i, j := l, l; i >= 0 && j < len(s); i, j = i-1, j+1 {
		if s[i] != s[j] {
			return long, true
		}
		long = j - i + 1
	}
	return long, true
}
func check2(l, r int, s string) (int, bool) {
	long := 0
	for i, j := l, r; i >= 0 && j < len(s); i, j = i-1, j+1 {
		if s[i] != s[j] {
			return long, true
		}
		long = j - i + 1
	}
	return long, true
}

//dp
func longestPalindrome(s string) string {
	n := len(s)
	// dp[i][j] 表示 s[i..j] 是否是回文串
	dp := make([][]bool, n)
	result := s[0:1]
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
		//所有长度为 1 的子串都是回文串
		dp[i][i] = true
	}
	//枚举子串长度
	for length := 2; length <= n; length++ {
		// 枚举左边界
		for i := 0; i < n; i++ {
			//确定右边界
			j := i + length - 1
			if j >= n {
				break
			}
			if s[i] == s[j] {
				if length <= 2 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			} else {
				dp[i][j] = false
			}
			//dp[i][j] == true 成立，就表示子串 s[i..j] 是回文
			if dp[i][j] == true && j-i+1 > len(result) {
				result = s[i : j+1]
			}
		}
	}
	return result
}