647. 回文子串
給你一個(gè)字符串?s?，請(qǐng)你統(tǒng)計(jì)并返回這個(gè)字符串中?回文子串?的數(shù)目。
回文字符串?是正著讀和倒過(guò)來(lái)讀一樣的字符串。
子字符串?是字符串中的由連續(xù)字符組成的一個(gè)序列。
具有不同開(kāi)始位置或結(jié)束位置的子串，即使是由相同的字符組成，也會(huì)被視作不同的子串。
思路：構(gòu)建dp數(shù)組，dp[i][j]代表s[i:j+1] 是否為回文子串（i<=j)。轉(zhuǎn)移方程：如果s[i]==s[j], 此時(shí)分為三種情況，如果 i==j, 則顯然為回文子串，如果i==j-1，則顯然也是回文子串（aa），如果i<j-1,則dp[i][j]=dp[i+1][j-1] (回文子串的前后加上相同的字母仍然是回文串）。初始化：因?yàn)橐粋€(gè)字母本身就是回文，所以對(duì)角線的元素初始化為1，其他則初始化為0。遍歷順序：由轉(zhuǎn)移方程，當(dāng)前元素依賴左下角的數(shù)據(jù)，所以遍歷順序?yàn)閺纳系较?，從左到? 使用result記錄true的個(gè)數(shù).
class Solution:
def countSubstrings(self, s: str) -> int:
dp = [[False]*len(s) for _ in range(len(s))]
for n in range(len(s)):
dp[n][n] = True
result = 0
for i in range(len(s) -1, -1, -1):
for j in range(i，len(s)):
if s[i] == s[j]:
if i>=j-1:
result+=1
dp[i][j] = True
else:
dp[i][j] = dp[i+1][j-1]
if dp[i][j]:
result += 1
return result
516. 最長(zhǎng)回文子序列
給你一個(gè)字符串?s?，找出其中最長(zhǎng)的回文子序列，并返回該序列的長(zhǎng)度。
子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個(gè)序列。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-728421.html
思路：與上題類似使用二維dp數(shù)組模擬字符串。dp[i][j]表示字符串s[i:j+1]的最長(zhǎng)回文子序列長(zhǎng)度。當(dāng)s[i]==s[j],dp[i][j] = dp[i+1][j-1] + 2, 如果不等于，則考慮將其中一個(gè)放到開(kāi)頭（或結(jié)尾）時(shí)的最長(zhǎng)子序列長(zhǎng)度文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-728421.html
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
for i in range(len(s)-1, -1, -1):
for j in range(i+1, len(s)):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][-1]到了這里，關(guān)于代碼隨想錄day59的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
