官方动态规划解决最长回文串问题代码解释:
class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) #字符串的总长度 if n < 2: return s #如果字符串长度为1,则s本身就是最长回文串 max_len = 1 #预设初始最大长度为1 begin = 0 # # dp[i][j] 表示 s[i..j] 是否是回文串 dp = [[False] * n for _ in range(n)] #得到的是一个每个位置都是False的n*n矩阵 for i in range(n): dp[i][i] = True #将对角线(对角线上是i到i,eg:11是s[1],22是s[2]......)上的False变为True,因为每个字符单独都是一个回文串。 # 递推开始 # 先枚举子串长度 for L in range(2, n + 1): #L是子串长度,长度区间是[2,n+1) #先确定子串长度,再确定左边界,这时候就可以求得右边界。 # 枚举左边界,左边界的上限设置可以宽松一些 for i in range(n): #i是左边界,j是右边界。范围都是[0,n-1] # 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得 j = L + i - 1 # 如果右边界越界,就可以退出当前循环 if j >= n: break if s[i] != s[j]: #子串的两端不相等,则此位置置False dp[i][j] = False else: if j - i < 3: #子串两端相等,有两种情况,一种是回文串,一种不是 dp[i][j] = True #子串长度是2、3时,边界值相等则此串是回文串。子串长度较长时,边界两值相等,不一定是回文串 else: dp[i][j] = dp[i + 1][j - 1] #长度较长时,如果dp[i+1][j-1]是回文串,此时左右两边的值又一样,那么dp[i][j]也是回文串 #所以s[i]=s[j]时,dp[i][j]和dp[i+1][j-1]的值相同 # 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置 if dp[i][j] and j - i + 1 > max_len: #如果dp[i][L]处是True,并且此时代表的子串长度大于当前最大子串长度, max_len = j - i + 1 #则更新当前最大长度 begin = i #begin是最长字串的起始长度 return s[begin:begin + max_len] #返回此最长回文串
[False]*n:
[False]*n得到由n个False组成的列表。eg:[False]*3 = [False,False,False]
for _ in range(n):
_是占位符,它可以代表任意变量,但我们不关心_具体是什么。
比如对于:
for i in range(n): return('Hello!')
这里我们并不需要i这个变量,我们只需要后面的循环n次,此时就可以用_来代替这个变量。