玉溪博客 触屏版

当前位置: 首页 > LeetCode > 正文

剑指offer 最长回文子串

又tm一天 c

func longestPalindrome(s string) string {
	var n =len(s)
	var dp = make([][]bool,n)
	var max = 1
	var start int
	for  i:= 0 ;i<n;i++ {
		dp[i] = make([]bool, n)
	}
	for j:=0;j<n;j++ {
		for i:=0;i<=j;i++ {
			if j-i <2 {
				dp[i][j] = (s[i] == s[j])
			}else {
				dp[i][j] = (dp[i+1][j-1] && s[i] == s[j])
			}

			if dp[i][j] && j-i+1>max{
				max = j-i+1
				start = i
			}
		}

	}
	return s[start:start+max]
}

注意到两个循环，必须要在保证判断dp[i][j]时，dp[i+1][j+1]里这个区间所有的元素都已经正确赋值，一开始写的循环“aaaaa”，一直报错，就是因为判断s[4]的时候，dp[0][3]虽然true了，但是dp[1][4]还是false，还有个问题就是之前的循环一个元素和两个字符比如“aa”这样的回文子串判断不出来，原因也是遍历不到位的原因，dp[i+1][j-1]还是原来那个元素，并没有正确赋值。