题解 | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af
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 }