成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Distinct Subsequences

Ajian / 3528人閱讀

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

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

終于見到一個(gè)使用動(dòng)態(tài)規(guī)劃的題目了，似乎這種字符串比對(duì)的差不多都是DP的思路。
這個(gè)問題實(shí)際上是問一個(gè)長(zhǎng)字符串中有幾個(gè)給定的子串，因此從開始比較，以最后一個(gè)字符為例，如果T的最后一個(gè)字符和S的最后一個(gè)字符不相同相同，那么問題就成為求字符串S[:-2]中字符T的個(gè)數(shù)；如果相同，問題就變?yōu)榍笞址?b>S[:-2]中字符T的個(gè)數(shù)和S[:-2]中子串T[:-2]的個(gè)數(shù)之和。從后向前遞推，我們可以得到下面的矩陣

    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

可以看出，矩陣中每個(gè)entry的數(shù)值為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]

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/37302.html

相關(guān)文章

  • [Leetcode] Distinct Subsequences 不同順序字串

    摘要：計(jì)算元素值時(shí)，當(dāng)末尾字母一樣，實(shí)際上是左方數(shù)字加左上方數(shù)字，當(dāng)不一樣時(shí)，就是左方的數(shù)字。示意圖代碼如果這個(gè)字符串有個(gè)怎么辦用暴力法，對(duì)每一位開始向后檢查是否是。 Distinct Subsequences Given a string S and a string T, count the number of distinct subsequences of T in S. A su...

    SnaiLiu 評(píng)論0 收藏0

  • leetcode115. Distinct Subsequences

    摘要：題目要求判斷字符串中通過刪減單詞含有幾個(gè)字符串。例如中含有個(gè)字符串，通過分別刪除第，，個(gè)。也就是說，我們需要通過一個(gè)數(shù)據(jù)結(jié)構(gòu)來記錄臨時(shí)結(jié)果從而支持我們?cè)谝阎懊鎺讉€(gè)情況的場(chǎng)景下對(duì)后續(xù)情況進(jìn)行計(jì)算。 題目要求 Given a string S and a string T, count the number of distinct subsequences of S which equa...

    NSFish 評(píng)論0 收藏0

  • [LintCode/LeetCode] Distinct Subsequences [一維DP]

    摘要：用動(dòng)規(guī)方法做建立長(zhǎng)度為和的二維數(shù)組，表示的第到位子串包含不同的的第到位子串的個(gè)數(shù)。初始化當(dāng)?shù)淖哟L(zhǎng)度為時(shí)，當(dāng)?shù)淖哟L(zhǎng)度為時(shí)，當(dāng)和子串都為時(shí)，包含，故。 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 評(píng)論0 收藏0

  • 115 Distinct Subsequences

    摘要：截取和出來填表。這里沒有新路徑產(chǎn)生，就是最大可能的值。 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 評(píng)論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 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<