03-05 2538人
又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]还是原来那个元素,并没有正确赋值。
欢迎留言