题解 | #最长回文子串#动态规划
最长回文子串
https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param A string字符串 # @return int整型 # class Solution: def getLongestPalindrome(self , A: str) -> int: # write code here n = len(A) ans = 1 dp = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): dp[i][i] = 1 for L in range(2, n + 1): # 遍历长度 L. !!! 一定要注意先遍历短的字符串 for l in range(n): # 遍历左边的索引 l r = l + L - 1 # 右边的索引 r if r > n - 1: break if A[l] != A[r]: dp[l][r] = 0 elif r - l + 1 <= 2: dp[l][r] = 1 else: dp[l][r] = dp[l + 1][r - 1] if dp[l][r] == 1: ans = max(ans, r - l + 1) return ans
算法之路 文章被收录于专栏
有关数据结构、算法等的文章