Distinct Subsequences

Ajian 发布于2019-07-24 17:32 / 3523人阅读

摘要：终于见到一个使用动态规划的题目了，似乎这种字符串比对的差不多都是的思路。从后向前递推，我们可以得到下面的矩阵可以看出，矩阵中每个的数值为，这样右下角的值即为所求。

Problem

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.

Solution

终于见到一个使用动态规划的题目了，似乎这种字符串比对的差不多都是DP的思路。
这个问题实际上是问一个长字符串中有几个给定的子串，因此从开始比较，以最后一个字符为例，如果T的最后一个字符和S的最后一个字符不相同相同，那么问题就成为求字符串S[:-2]中字符T的个数；如果相同，问题就变为求字符串S[:-2]中字符T的个数和S[:-2]中子串T[:-2]的个数之和。从后向前递推，我们可以得到下面的矩阵

    r a b b b i t

  1 1 1 1 1 1 1 1

r 0 1 1 1 1 1 1 1

a 0 0 1 1 1 1 1 1

b 0 0 0 1 2 3 3 3

b 0 0 0 0 1 3 3 3

i 0 0 0 0 0 0 3 3

t 0 0 0 0 0 0 0 3

可以看出，矩阵中每个entry的数值为match[i][j] = match[i][j-1] + (match[i-1][j-1] if S[j-1] == T[i-1] else 0)，这样右下角的值即为所求。

AC代码如下：

class Solution:
    # @return an integer
    def numDistinct(self, S, T):
        length_s = len(S)
        length_t = len(T)
        if length_s == 0:
            return 0 if length_t != 0 else 1
        if length_t == 0:
            return 1
        match = [[0 for dummy_i in range(length_s + 1)] for dummy_j in range(length_t + 1)]
        for col in range(length_s + 1):
            match[0][col] = 1
        for s_idx in range(1, length_s + 1):
            for t_idx in range(1, length_t + 1):
                match[t_idx][s_idx] = match[t_idx][s_idx - 1]
                if S[s_idx - 1] == T[t_idx - 1]:
                    match[t_idx][s_idx] += match[t_idx - 1][s_idx - 1]
        return match[length_t][length_s]

云服务器 GPU云服务器 Subsequences Distinct distinct去重 sql中distinct

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

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

[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
leetcode115. Distinct Subsequences

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

NSFish 2019-08-16 10:44 评论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
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] 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