嘉兴互联网公司,常州百度推广优化,专业品牌设计网站建设,软件外包交易平台这里写目录标题 647. 回文子串516.最长回文子序列总结 647. 回文子串
1.动态规划和2.中心扩展 这个视频是基于上面的视频的代码
方法1:动态规划 布尔类型的dp[i][j]#xff1a;表示区间范围[i,j] #xff08;注意是左闭右闭#xff09;的子串是否是回文子串#xff0c;如… 这里写目录标题 647. 回文子串516.最长回文子序列总结 647. 回文子串
1.动态规划和2.中心扩展 这个视频是基于上面的视频的代码
方法1:动态规划 布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果是dp[i][j]为true否则为false。 dp[i][j] (c[i] c[j]) ( (j-i2) || dp[i1][j-1] );
class Solution {public int countSubstrings(String s) {char[] c s.toCharArray();int n c.length;boolean[][] dp new boolean[n][n];int count 0;for(int j0;jn;j){for(int i0;ij;i){dp[i][j] (c[i] c[j]) ( (j-i2) || dp[i1][j-1] );if(dp[i][j]) count;}}
return count;}
}方法2:中心扩展法 只有两种情况1.以单个字母为中心 2. 以两个字母为中心
class Solution {int count 0;public int countSubstrings(String s) {for(int i0;is.length();i){helper(s,i,i);helper(s,i,i1);}return count;}public void helper(String s, int left, int right){while(left0rights.length()s.charAt(left) s.charAt(right)){count;left--;right;}}
}516.最长回文子序列
两种思路
思路一求当前序列 和 反转之后的 最长公共子序列 就是这道题1146一摸一样了 dp[i][j] 表示s1的前i个字符和s2的前j个字符最长…
class Solution {public int longestPalindromeSubseq(String s) {char[] A s.toCharArray();char[] B new char[A.length];for(int i0;iA.length;i){B[i] A[A.length -1-i];}int[][] dp new int[A.length1][A.length1];for(int i1;iA.length;i){for(int j 1;jA.length;j){if(A[i-1] B[j-1]){dp[i][j] dp[i-1][j-1]1;}else{dp[i][j] Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[A.length][B.length];}
}思路二区间DP 子序列的本质就是选与不选 dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。 超出时间限制的递归
将递归变成循环
class Solution {public int longestPalindromeSubseq(String s) {char[] A s.toCharArray();int n A.length;int[][] dp new int[n][n];for(int i n-1;i0;i--){dp[i][i] 1; //2. ij for(int ji1;jn;j){ //3.jiif(A[i] A[j]){dp[i][j] dp[i1][j-1]2;}else{dp[i][j] Math.max(dp[i1][j],dp[i][j-1]);}}}return dp[0][n-1];}
}总结
