[LeetCode] 115. Distinct Subsequences_ Hard tag: Dynamic Programming

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).

Example 1:

Input: S = "rabbbit", T = "rabbit"

Output: 3

Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.

(The caret symbol ^ means the chosen letters)

rabbbit

^^^^ ^^

rabbbit

^^ ^^^^

rabbbit

^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"

Output: 5

Explanation:

As shown below, there are 5 ways you can generate "bag" from S.

(The caret symbol ^ means the chosen letters)

babgbag

^^ ^

babgbag

^^    ^

babgbag

^    ^^

babgbag

  ^  ^^

babgbag

    ^^^

这个题目思路是用两个sequence的dynamic programming，mem[l1 + 1][l2 + 1] # mem[i][j]表示number of distinct subsequences of S[: i + 1] which equals T[: j + 1]
mem[i][j] = mem[i - 1][j] + mem[i - 1][j - 1]   if s1[i - 1] == s2[j - 1]   # 如果相等，可以选择配对或者不配对
　　　　　　  mem[i - 1][j]                       if s1[i - 1] != s2[j - 1]   # 如果不相等，就必须把最后一个舍弃掉

初始化： mem[i][0] = 1,  mem[0][j] = 0 (j > 1)

code

class Solution:

    def disSubsequences(self, s1, s2):

        l1, l2 = len(s1), len(s2)

        mem = [[0] * (l2 + 1) for _ in range(l1 + 1)]

        for i in range(l1 + 1):

            mem[i][0] = 1

        for i in range(1, l1 + 1):

            for j in range(1, l2 + 1):

                mem[i][j] = mem[i - 1][j] if s1[i - 1] != s2[j - 1] else mem[i - 1][j] + mem[i - 1][j - 1]

        return mem[l1][l2]

巴特西

[LeetCode] 115. Distinct Subsequences_ Hard tag: Dynamic Programming

最新文章

热门文章