本文共 1813 字，大约阅读时间需要 6 分钟。

• ：求字符串中最大回文子串（不一定连续）的最大长度

将s翻转成s1 求s和s1的最长公共子序列长度

可以先判断下s是否是回文

另外一个思路

dp[i][j] = dp[i + 1][j - 1] + 2 if s[i] == s[j]

dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) otherwise

class Solution(object):    def longestPalindromeSubseq(self, s):        """        :type s: str        :rtype: int        """        size = len(s)        s1 = s[::-1]        if s1 == s: return size        dp = [[0]*(size+1) for i in range(size+1)]        for i in range(size):            for j in range(size):                if s[i]==s1[j]:                     dp[i+1][j+1] = dp[i][j]+1                else:                    dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])        return dp[size][size]

• ：求最长回文子串，Medium

在每个字符的两边都插入一个特殊的符号’#’

定义 id 为已知的 {右边界最大} 的回文子串的中心，mx则为id+P[id]，也就是这个子串的右边界

class Solution(object):    def longestPalindrome(self,s):        '''        :param s: str        :return: str        '''        ss = '$';idx=0;mx=0        for i in s:            ss = ss+'#'+i        ss = ss+'#'        P = [0 for i in range(len(ss))]        for i in range(1,len(ss)):            if P[idx]+idx
   
    P[mx]:                mx = i        a = ss[mx - (P[mx] - 1):mx + P[mx]]        ret = ''        for i in a:            if i!='#':                ret+=i        return ret
   

• 求一个字符串中回文子字符串的总个数，Medium

判断s[i:j+1]是否是回文等价于判断s[i+1:j] 和 s[i][j]的情况

class Solution(object):    def countSubstrings(self, s):        """        :type s: str        :rtype: int        """        if s=='': return 0        size = len(s)        dp = [[0 for i in range(size)] for j in range(size)]        ret = 0        for i in range(size):            dp[i][i]=1            for j in range(i):                if s[i]==s[j]:                    if dp[i-1][j+1] or j==i-1:                        dp[i][j] = 1            ret += sum(dp[i])        return ret

To do list

转载地址：http://gfqmi.baihongyu.com/