Distinct Subsequences

Ajian 發布于2019-07-24 17:32 / 3519人閱讀

摘要：終于見到一個使用動態規劃的題目了，似乎這種字符串比對的差不多都是的思路。從后向前遞推，我們可以得到下面的矩陣可以看出，矩陣中每個的數值為，這樣右下角的值即為所求。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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