新博文地址:[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()]; }
相关推荐
115.Distinct_Subsequences不同的子序列【LeetCode单题讲解系列】
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
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](./...
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
vs code LeetCode 插件
leetcode中文版
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
100个leetCode详细解答
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/...
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案
leetcode高频面试笔试题150+道,亲身总结。