- 浏览: 89434 次
- 性别:
- 来自: 南京
最新评论
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
.
方法:dp
a[i][j]表示T中前j个在S的前i个出现的个数。
则
if S[i] != T[j]
a[i][j] = a[i-1][j],相当于如果S中前i-1个可以表示T中前j个的话,那么多一个S[i]也不会影响。
if S[i] == T[j]
a[i][j] = a[i-1][j] + a[i-1][j-1]
class Solution { public: int numDistinct(string S, string T) { int* a = new int[T.size()]; memset(a, 0, sizeof(int) * T.size()); for (int i = 0; i < S.size(); i++) { for (int j = T.size()-1; j >= 0; j--) { if (S[i] == T[j]) { if (j==0) a[j] += 1; else a[j] += a[j-1]; } } } return a[T.size()-1]; } };
发表评论
-
[Leetcode] Gas Station
2013-10-07 00:02 929Gas Station AC Rate: 101 ... -
[Leetcode] Word Break 1 & 2
2013-10-05 23:26 1376Word Break AC Rate: 2/1 ... -
[Leetcode] Single Number 1 & 2
2013-10-05 22:50 2765Single Number AC Rat ... -
[Leetcode] Copy List with Random Pointer
2013-10-05 22:43 587Copy List with Random Pointe ... -
[Leetcode] Path Sum
2013-10-03 23:52 599Path Sum AC Rate: 87 ... -
[Leetcode] Remove Duplicates from Sorted List 1 & 2
2013-10-03 23:34 981Remove Duplicates from Sort ... -
[Leetcode] Scramble String
2013-10-03 16:55 1843Scramble String AC Rate ... -
[Leetcode] Partition List
2013-09-29 23:38 669Partition List AC Rate: ... -
[Leetcode] Word Search
2013-09-21 23:21 861Given a 2D board and ... -
[Leetcode] Decode Ways
2013-09-11 17:33 692Decode WaysJun 25 '126747 / 2 ... -
[Leetcode] Convert Sorted List to Binary Search Tree
2013-09-11 16:06 722Convert Sorted List to Binary ... -
[Leetcode] Binary Tree Level Order Traversal
2013-09-10 14:39 787Binary Tree Level Order Trave ... -
[Leetcode] Subsets 1 ^& 2
2013-09-09 21:42 875SubsetsApr 18 '126226 / 1626 ... -
[Leetcode] Unique Paths II
2013-09-09 21:10 768Unique Paths IIMar 29 '124573 ... -
[Leetcode] Flatten Binary Tree to Linked List
2013-09-09 02:35 731Flatten Binary Tree to Linked ... -
[Leetcode] Triangle
2013-09-04 16:32 934TriangleOct 30 '126503 / 1779 ... -
[Leetcode] Balanced Binary Tree
2013-08-27 20:53 614Balanced Binary TreeOct 9 '12 ... -
[Leetcode] Rotate Image
2013-08-22 15:54 980Rotate ImageMar 18 '124182 / ... -
[Leetcode] Permutations / Permutations II
2013-08-22 15:41 2512Permutations IIMar 17 '12494 ... -
[Leetcode] Jump Game / Jump Game II
2013-08-22 10:31 663Jump GameMar 25 '126923 / 162 ...
相关推荐
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+道,亲身总结。