leetcode115. Distinct Subsequences

NSFish 发布于2019-08-16 10:44 / 2835人阅读

摘要：题目要求判断字符串中通过删减单词含有几个字符串。例如中含有个字符串，通过分别删除第，，个。也就是说，我们需要通过一个数据结构来记录临时结果从而支持我们在已知前面几个情况的场景下对后续情况进行计算。

题目要求

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

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.

判断S字符串中通过删减单词含有几个T字符串。例如rabbbit中含有3个rabbit字符串，通过分别删除第1，2，3个b。

思路和代码

这时一道典型的DP题。也就是说，我们需要通过一个数据结构来记录临时结果从而支持我们在已知前面几个情况的场景下对后续情况进行计算。在这道题目中，如果我们想要计算S中含有几个T（假设S长度为n，T长度为m），那么我们只需要知道S[0...n]含有几个T[0...m-1]以及S[0...n-1]含有几个T[0...m-1]。
从中归纳出最普遍的场景，也就是如果想要计算S[0...i]含有几个T[0...j]，可以从以下两种场景来考虑：

1.S[i]!=T[j]
那么S[0...i]包含的T[0...j]的数量等价于S[0...i-1]包含T[0...j]的数量。
2.S[i]==T[j]
那么S[0...i]包含的T[0...j]的数量等价于S[0...i-1]包含T[0...j]的数量**加上**S[0...i-1]包含T[0...j-1]的数量

再来考虑初始的极端情况

1.j==0，此时S为一个空字符串，那么S的任何自字符串都包含一个唯一空字符串
2.i==0&&j！=0 此时S为非空字符串而T为空字符串，那么S包含0个T

之后我们采用intm+1来存储临时变量，其中inti+1表示S[0...j]含有几个T[0...i]
代码如下：

    public int numDistinct(String s, String t) {
        if(s==null || t==null) return 0;
        if(t.isEmpty()) return 1;
        int[][] temp = new int[t.length()+1][s.length()+1];
        for(int i = 0 ; i
对这段代码的优化我们可以考虑不采用二维数组而采用一维数组的方式来存储过程值：
    public int numDistinct2(String s, String t) {
        int[] array = new int[s.length()+1];
        int prev = 1;
        for(int i = 0 ; i

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云云服务器 Subsequences Leetcod LeetCode Distinct

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70346.html

115 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 str...

LittleLiByte 2019-08-14 17:59 评论0 收藏0
[Leetcode] Distinct Subsequences 不同顺序字串

摘要：计算元素值时，当末尾字母一样，实际上是左方数字加左上方数字，当不一样时，就是左方的数字。示意图代码如果这个字符串有个怎么办用暴力法，对每一位开始向后检查是否是。 Distinct Subsequences Given a string S and a string T, count the number of distinct subsequences of T in S. A su...

SnaiLiu 2019-08-14 16:11 评论0 收藏0
[LintCode/LeetCode] Distinct Subsequences [一维DP]

摘要：用动规方法做建立长度为和的二维数组，表示的第到位子串包含不同的的第到位子串的个数。初始化当的子串长度为时，当的子串长度为时，当和子串都为时，包含，故。 Problem Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a strin...

dailybird 2019-08-14 15:29 评论0 收藏0
Distinct Subsequences

摘要：终于见到一个使用动态规划的题目了，似乎这种字符串比对的差不多都是的思路。从后向前递推，我们可以得到下面的矩阵可以看出，矩阵中每个的数值为，这样右下角的值即为所求。 Problem Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of...

Ajian 2019-07-24 17:32 评论0 收藏0
[LeetCode] 491. Increasing Subsequences

Problem Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 . Example: ...

wupengyu 2019-08-16 13:50 评论0 收藏0