新博文地址:[leetcode]Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
这道题递归是肯定要超时的,参考了难度表,提示用DP,好吧,实在不解,还是google吧。看了很多博客的解法,几乎都是一模一样的,就不再啰嗦,实在不明白了就看这篇吧。
copy代码如下:
public int numDistinct(String S, String T) { int[][] dp = new int[T.length() + 1][S.length() + 1]; dp[0][0] = 1; for(int i = 1 ; i <= S.length(); i++){ dp[0][i] = 1; } for(int i = 1 ; i <= T.length(); i++){ dp[i][0] = 0; } for (int i = 1; i <= T.length(); i++) { for(int j = 1; j <= S.length(); j++){ dp[i][j] = dp[i][j - 1]; if(T.charAt(i - 1) == S.charAt(j - 1)){ dp[i][j] += dp[i - 1][j - 1]; } } } return dp[T.length()][S.length()]; }
相关推荐
java java_leetcode题解之Distinct Subsequences.java
115.Distinct_Subsequences不同的子序列【LeetCode单题讲解系列】
python python_leetcode题解之115_Distinct_Subsequences
javascript js_leetcode题解之115-distinct-subsequences.js
leetcode 分类 LeetCode Progress 128/154 Other Solutions ...Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态规划-Longest Valid Parentheses](./leetcode/动态规划-Longest Valid Parentheses.java) [动态规划-Maximum Length of Repeated Subarray](./...
10. leetcode-115-Distinct-Subsequences.md:第115题,不同的子序列,涉及到动态规划和字符串处理。 这些题目覆盖了各种算法和数据结构,包括字符串处理、动态规划、树结构遍历、数组处理、位运算、深度优先搜索、...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
java lru leetcode ##Thinking in Java chapter21 ##Netty in Action ####chapter2: ...Subsequences] () [Rotate Image] () [Ugly Number] () [Ugly Number II] () [Repeated DNA Sequences] () [Lar
leetcode卡 OJ 题目汇总 记录下自己做过的oj题目, 也记录下自己对算法以及编程的理解与...Subsequences两种解法解题失败 [] 2014-06-14-13:00 ~ 2014-06-14-14:40 Interleaving String动态规划解决, Recovering BST失败
Distinct Subsequences、152. Maximum Product Subarray等。这类题目通常要求读者使用动态规划来解决问题,例如使用DP数组来记录状态、使用递归来计算结果等。 6. 排序和查找类题目 排序和查找类题目是LeetCode原...
gas station leetcode 在牛客网上的在线编程中的leetcode在线编程题解 代码中有详细题解 完成: 树 Minimum Depth ...distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
10. **Distinct Subsequences** (不同的子序列) 统计一个字符串所有非空子序列在另一个字符串中出现的次数。动态规划方法,考虑当前字符是否出现在子序列中。 11. **Largest Rectangle in Histogram** (柱状图中...