代码随想录 Day54 - 动态规划(十五)
作者:jjn0703
- 2023-08-26 江苏
本文字数:1000 字
阅读完需:约 3 分钟
作业题
392.判断子序列
链接:https://leetcode.cn/problems/is-subsequence/description/
package jjn.carl.dp;
import java.util.Scanner;
/**
* @author Jjn
* @since 2023/8/26 11:06
*/
public class LeetCode392 {
public boolean isSubsequence(String s, String t) {
int firstIndex = 0;
int secondIndex = 0;
while (secondIndex < t.length() && firstIndex < s.length()) {
if (t.charAt(secondIndex) == s.charAt(firstIndex)) {
firstIndex++;
}
secondIndex++;
}
return firstIndex >= s.length();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
String t = scanner.next();
boolean isSubsequence = new LeetCode392().isSubsequence(s, t);
System.out.println(isSubsequence);
}
}
复制代码
115.不同的子序列
链接:https://leetcode.cn/problems/distinct-subsequences/description/
package jjn.carl.dp;
import jjn.round1.LeetCode171_ExcelSheetColumnNumber;
import java.util.Scanner;
/**
* @author Jjn
* @since 2023/8/26 11:29
*/
public class LeetCode115 {
public int numDistinct(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
for (int i = 0; i <= s.length(); i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= t.length(); j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.length()][t.length()];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
String t = scanner.next();
int distinct = new LeetCode115().numDistinct(s, t);
System.out.println(distinct);
}
}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/af10855963e99a4cf8691cdfa】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
![用户头像](http://static001.geekbang.org/account/avatar/00/10/6d/ac/6128225f.jpg?x-oss-process=image/resize,w_200,h_200)
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论