自己做网站和推广,wordpress自动分类插件,网站开发资源,编程培训班哪个好LeetCode 67 回文子串 思路很简单#xff0c;每一个dp[i]等于dp[i-1]加上当前字符向前直到0各个长度字符串回文串个数即可
代码如下#xff1a;
class Solution {public boolean isValid(String s) {int l 0, r s.length() - 1;while (l r) {if (s.charAt(l) ! s.ch…LeetCode 67 回文子串 思路很简单每一个dp[i]等于dp[i-1]加上当前字符向前直到0各个长度字符串回文串个数即可
代码如下
class Solution {public boolean isValid(String s) {int l 0, r s.length() - 1;while (l r) {if (s.charAt(l) ! s.charAt(r)) return false;l; r--;}return true;}public int countSubstrings(String s) {int[] dp new int[s.length()];dp[0] 1;for (int i 1; i s.length(); i) {dp[i] dp[i-1];for (int j i; j 0; j--) {String ss s.substring(j, i1);if (isValid(ss)) dp[i]; }}return dp[s.length() - 1];}
} LeetCode 516 最长回文子序列 这题要在上一题基础上稍微转换下思路。
原本是从前往后循环内从后往前统计回文字符串数目这题是从中间往两边看两边分别接触到的第一个字符是否相等。
如果相等就都放入并且dp[i][j]等于dp[i1][j-1]2否则dp[i][j]取dp[i1][j]、dp[i][j-1]、dp[i][j]中最大值即可。这就是这道题的递推逻辑了。
初始化方式是在ij时要初始化为1。或者将dp[i][i]初始化为1也行
从递归公式中可以看出dp[i][j] 依赖于 dp[i 1][j - 1] dp[i 1][j] 和 dp[i][j - 1]如图 所以遍历i的时候一定要从下到上遍历这样才能保证下一行的数据是经过计算的。
代码如下
public class Solution {public int longestPalindromeSubseq(String s) {int len s.length();int[][] dp new int[len 1][len 1];for (int i len - 1; i 0; i--) { // 从后往前遍历 保证情况不漏dp[i][i] 1; // 初始化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], Math.max(dp[i][j], dp[i][j - 1]));}}}return dp[0][len - 1];}
}
