题解 | #最长回文子串#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param A string字符串
 * @return int整型
 */
/*
func ifIJSeqIsValid(A string, i, j int) bool {
	isValid := true
	p1, p2 := i, j
	for p1 <= p2 {
		if A[p1] != A[p2] {
			isValid = false
			break
		}
		p1++
		p2--
	}
	return isValid
}

func getLongestPalindrome(A string) int {
	// write code here
	if len(A) < 2 {
		return len(A)
	}
	mxLen := 1
	//判断
	for i := 0; i < len(A); i++ {
		for j := 0; j < len(A); j++ {
			isValid := ifIJSeqIsValid(A, i, j)
			if isValid && j-i+1 > mxLen {
				mxLen = j - i + 1
			}
		}
	}
	return mxLen
}
*/
func getLongestPalindrome(A string) int {
	// write code here
	if len(A) < 2 {
		return len(A)
	}
	mxLen := 1
	//记录任意两个字符位置之间是否是回文子串
	dp := make([][]bool, len(A))
	for i := 0; i < len(A); i++ {
		dp[i] = make([]bool, len(A))
		dp[i][i] = true
	}
	//判断;要注意顺序，保证访问dp[i][j]的时候，依赖的dp[i+1][j-1]已经是被访问过的； -> dp[i][j]表示以i为开始的，以j为结尾的字符串是否是回文串；
	//访问j-1的时候要保证j-1已经访问过；j采用递减的方式
	//访问i+1的时候要保证i+1已经访问过；i采用底层的方式
	for j := 1; j < len(A); j++ { //开始位置
		for i := j - 1; i >= 0; i-- { //结束位置；循环的顺序不能颠倒，先确定结束字符再确定开始字符
			if j-i == 1 {
				dp[i][j] = A[i] == A[j]
			} else {
				dp[i][j] = dp[i+1][j-1] && A[i] == A[j] //这里：j-1的时候；上面已经文芳过；i+1的时候i已经问过
			}
			if dp[i][j] && j-i+1 > mxLen {
				mxLen = j - i + 1
			}
		}
	}
	return mxLen
}