Distinct Subsequences

Ajian 發(fā)布于2019-07-24 17:32 / 3527人閱讀

摘要：終于見(jiàn)到一個(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

終于見(jiàn)到一個(gè)使用動(dòng)態(tài)規(guī)劃的題目了，似乎這種字符串比對(duì)的差不多都是DP的思路。
這個(gè)問(wèn)題實(shí)際上是問(wèn)一個(gè)長(zhǎng)字符串中有幾個(gè)給定的子串，因此從開(kāi)始比較，以最后一個(gè)字符為例，如果T的最后一個(gè)字符和S的最后一個(gè)字符不相同相同，那么問(wèn)題就成為求字符串S[:-2]中字符T的個(gè)數(shù)；如果相同，問(wèn)題就變?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]