代码随想录算法训练营第46天 | 647. 回文子串、516.最长回文子序列

647. 回文子串

题目链接：. - 力扣（LeetCode）

func countSubstrings(s string) int {dp:=make([][]bool,len(s))arr:=make([]bool,len(s))for i:=range dp{dp[i]=append([]bool{},arr...)}res:=0for i:=len(dp)-1;i>=0;i--{for j:=i;j<len(dp[i]);j++{if s[i]==s[j]{if j-i<=1{res++dp[i][j]=true} else if dp[i+1][j-1] {res++dp[i][j]=true}}}}return res
}

516.最长回文子序列

题目链接：. - 力扣（LeetCode）

func longestPalindromeSubseq(s string) int {dp:=make([][]int,len(s))arr:=make([]int,len(s))for i:=range dp{dp[i]=append([]int{},arr...)dp[i][i]=1}for i:=len(s)-1;i>=0;i--{for j:=i+1;j<len(s);j++{if s[i]==s[j]{dp[i][j]=dp[i+1][j-1]+2}else{dp[i][j]=max(dp[i][j-1],dp[i+1][j])}}}return dp[0][len(s)-1]
}