网站首页 LeetCode

剑指offer 最长回文子串

发布时间:2021-3-5 15:42 Friday编辑:admin阅读(337)

    又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]还是原来那个元素,并没有正确赋值。