题解 | #最长回文子串#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 描述
 * 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度
 *
 * @param A string字符串
 * @return int整型
 */
func getLongestPalindrome(A string) int {
	// 回文字串长度，即正反都是相同的字符
	// dp[i][j] 表示 字符串索引i～j的子串是否是回文串，如果是dp[i][j] = true 否则 为false
	// 状态转移方程：
	// 如果 s[i] == s[j]，且子串 s[i+1...j-1] 是回文串，那么 s[i...j] 也是回文串，即 dp[i][j] = true，其中 s[i] 和 s[j] 是字符串 s 的第 i 和第 j 个字符。
	// 对于只有一个字符的情况，即 i == j，dp[i][j] = true。
	// 对于两个相邻字符的情况，即 j == i + 1，如果 s[i] == s[j]，则 dp[i][j] = true

	n := len(A)
	if n == 0 {
		return 0
	}

	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}

	longest := 1
	for i := 0; i < n; i++ {
		dp[i][i] = true
	}

	for length := 2; length <= n; length++ {
		for start := 0; start <= n-length; start++ {
			end := start + length - 1
			if A[start] == A[end] {
				if length == 2 || dp[start+1][end-1] {
					dp[start][end] = true
					longest = length
				}
			}
		}
	}
	return longest
}