[LeetCode] 115. Distinct Subsequences

轉自LeetCode

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

It is guaranteed the answer fits on a 32-bit signed integer.

 

Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
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.
babgbag
babgbag
babgbag
babgbag
babgbag

 

Constraints:

• 1 <= s.length, t.length <= 1000
• s and t consist of English letters.

Solution

subsequence 的問題，通常會是用 DP 來解決

用 dp[i][j] 表示 s[0, j] 可以組成多少個 t[0, i] subsequence

初始的時候，將長度都加 1，因為要考慮空字串的情況

dp[0][j]，代表的是 s[0, j] 可以組成幾個空字串，所以值都會是 1

接下來考慮兩種狀況

t[i] != s[j] 的時候，代表多了 s[j] 也不會影響任何事，所以 dp[i][j] = dp[i][j-1]

t[i] = s[j] 的時候，可以想成 t[0,i]可以從 s[0, j-1] + s[j] 組成 或者 上一次的組成數目 + s[j] 組成

因此 dp[i][j] = dp[i][j-1] + dp[i-][j-1]

kotlin