代码随想录算法训练营第六十天| 647. 回文子串、516.最长回文子序列
647. 回文子串
题目链接:. - 力扣(LeetCode)
解题思路:注意遍历,要先遍历左下角元素
java:
class Solution {
public int countSubstrings(String s) {
int dp[][]=new int[s.length()][s.length()];
int count=0;
for(int i=s.length()-1;i>=0;i--){
for(int j=i;j<s.length();j++){
if(s.charAt(i)==s.charAt(j)){
if(j-i<=1){
dp[i][j]=1;
count++;
}
else{
if(dp[i+1][j-1]==1){
dp[i][j]=1;
count++;
}
}
}
}
}
return count;
}
}
516.最长回文子序列
题目链接:. - 力扣(LeetCode)
解题思路:还是左下角遍历
java:
class Solution {
public int longestPalindromeSubseq(String s) {
int len=s.length();
int dp[][]=new int[len][len];
for(int i=0;i<len;i++)
dp[i][i]=1;
for(int i=len-1;i>=0;i--){
for(int j=i+1;j<len;j++){
if(s.charAt(i)==s.charAt(j)){
dp[i][j]=dp[i+1][j-1]+2;
}
else
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][len-1];
}
}
原文地址:https://blog.csdn.net/m0_56545264/article/details/136472140
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!