网站搜索框怎么做,兰溪市建设局官方网站,软件工程就业岗位,建设网站公司哪里好相关的热搜问题解决方案所用代码 java 判断子序列 LeetCode 392
题目链接#xff1a;判断子序列 LeetCode 392 - 简单
思路
这题和之前求最长公共子序列一样。 dp[i] [j]#xff1a;以i-1为结尾的字符串s 和 以j-1为结尾的字符串t 组成的相同子序列的长度 递推公式#xff1a; 相等dp[i][j] d… 所用代码 java 判断子序列 LeetCode 392
题目链接判断子序列 LeetCode 392 - 简单
思路
这题和之前求最长公共子序列一样。 dp[i] [j]以i-1为结尾的字符串s 和 以j-1为结尾的字符串t 组成的相同子序列的长度 递推公式 相等dp[i][j] dp[i-1][j-1]不相等 dp[i][j] dp[i][j-1] 初始化0行0列无意义初始化为0 遍历顺序 打印dp
class Solution {public boolean isSubsequence(String s, String t) {int n1 s.length();int n2 t.length();int[][] dp new int[n11][n21];for (int i 1; i n1; i) {for (int j 1; j n2; j) {if (s.charAt(i-1) t.charAt(j-1)){dp[i][j] dp[i-1][j-1] 1;}else {dp[i][j] dp[i][j-1];}}
// System.out.println(Arrays.toString(dp[i]));}return dp[n1][n2] n1;}
}总结
本题和昨天的最长公共子序列几乎一模一样甚至更简单一点。因为我们只用判断字符串s是不是子序列就行了而不用去两个字符串里面找相同的子序列。
不同的子序列 LeetCode 115
题目链接不同的子序列 LeetCode 115 - 困难
思路
无。 s里面如何删除元素可以得到t dp[i] [j]以i-1为结尾的s中有以j-1为结尾的t的个数为dp[i] [j] 递推公式 相等 if(s[i-1] t[j-1]) 使用i-1dp[i][j] dp[i-1][j-1]不使用i-1dp[i-1][j]不用考虑是否使用t因为t是子串 不等 else dp[i][j] dp[i-1][j] 初始化 第一行(子串空字符串所以主串只有全部删完的情况) dp[i][0] 1第一列(主串s为空串所以没有能匹配的情况) dp[0][j] 0dp[0][0] 1 打印dp
class Solution {public int numDistinct(String s, String t) {int n1 s.length();int n2 t.length();int[][] dp new int[n11][n21];// 初始化// n10, 即空串中包含子序列t的情况为0// n20, 即s中包含子序列为空串的情况为1// n10,n22, 即空串中包含空串的情况为1for (int i 0; i n1; i) {dp[i][0] 1;}
for (int i 1; i n1; i) {for (int j 1; j n2; j) {if (s.charAt(i-1) t.charAt(j-1)){// 相等的情况由双方的上一位加上s的上一位决定删掉s对应的数dp[i][j] dp[i-1][j-1] dp[i-1][j];}else {// 不相等的情况由s的上一位觉得删掉s对应的数dp[i][j] dp[i-1][j];}}}return dp[n1][n2];}
}总结
我们可以打印出来dp数组以便更好的理解该题上侧还有一种i0的情况全为0(0,0为1)
Finished:Your input:babgbagbagOutput:5Expected:5stdout:1 0 0 0[1, 1, 0, 0][1, 1, 1, 0][1, 2, 1, 0][1, 2, 1, 1][1, 3, 1, 1][1, 3, 4, 1][0, 3, 4, 5]可以看到s的第一个字母b和t的第一个字母b一样所以匹配成功即dp[1][1] 1
然后s的第一个字母b和t的第二个字母a不匹配所以应看s的前一个字母上一行即dp[1][2] 0
最后s的第一个字母b和t的第三个字母g不匹配所以dp[1][2] 0
…
我们看s取第二个b的时候也就是第三行数据由于t的第一个字母也是b匹配成功即dp[3][1]等于双方各删一个值的情况t删了为空串匹配结果为1加 仅s删一个值的情况回退一位到s取a此时s为ba.gbgab也前面也有传递的结果1)所以dp[3][2] 2
…
…
我们每次都这样往后推相等即都删掉一个数不等即为s删掉一个数把前面的结果往后利用就可以得到包含所有子串的数量。
