写点什么

【LeetCode】不同的子序列 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 03 月 17 日

题目


给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。


字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)


题目数据保证答案符合 32 位带符号整数范围。


代码


public class DayCode {    public static void main(String[] args) {        String s = "";        String t = "";        int ans = new DayCode().numDistinct(s, t);        System.out.println(ans);    }
/** * https://leetcode-cn.com/problems/distinct-subsequences/comments/ * 时间复杂度 O(m * n) * 空间复杂度 O(m * n) * @param s * @param t * @return */ public int numDistinct(String s, String t) { int m = s.length(), n = t.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) { dp[i][0] = 1; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (j > i) { continue; } 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[m][n]; }}
复制代码


总结

  • 今天的 LeetCode 题目是 hard 题目,题目的类型是 hard。这个题目是动态规划的应用,需要用心去找转移方程。

  • 先根据题目构建图,得到初始值,然后将测试 case 带入,分析相等和不相等的情况,找出动态转移方程。

  • 题目还是需要反复思考,过变数,加深理解和思考。

  • 坚持每日一题,加油!


发布于: 2021 年 03 月 17 日阅读数: 8
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】不同的子序列Java题解