# 115. Distinct Subsequences

### 題目敘述

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.

#### 題目翻譯

``````rabbbit
..x
rabbbit
...x
rabbbit
....x
``````

### 解法解析

 r a b b b i t r 1 1 1 1 1 1 1 a 0 1 1 1 1 1 1 b 0 0 1 2 3 1 1 b 0 0 0 1 3 3 3 i 0 0 0 0 1 3 3 t 0 0 0 0 0 0 3

#### 程式範例

##### Python
``````class Solution:
def numDistinct(self, s: str, t: str) -> int:
m = len(t)
n = len(s)
if m > n:
return 0
elif m == n:
return int(s == t)

dp = [c == t[0] for c in s]
for c in t[1:]:
count = 0
for j in range(n):
temp = dp[j]
dp[j] = count if s[j] == c else 0
count += temp

return sum(dp)
``````
##### JavaScript
``````/**
* @param {string} s
* @param {string} t
* @return {number}
*/
var numDistinct = function (s, t) {
const m = t.length,
n = s.length;
const dp = new Array(m + 1).fill(0);

dp[0] = 1;

for (let i = 1; i < n + 1; i++) {
let prev = 1;
for (let j = 1; j < m + 1; j++) {
let temp = dp[j];
dp[j] += t[j - 1] === s[i - 1] ? prev : 0;
prev = temp;
}
}

return dp[m];
};
``````
##### Go
``````func numDistinct(s string, t string) int {
if len(s) < len(t) {
return 0
}

m, n := len(s), len(t)
dp := make([]int, n+1)
dp[0] = 1
for i := 1; i <= m; i++ {
for j := min(i, n); j > 0; j-- {
if s[i-1] == t[j-1] {
dp[j] += dp[j-1]
}
}
}
return dp[n]
}

func min(x, y int) int {
if x < y {
return x
}
return y
}
``````
##### Swift
``````class Solution {
func numDistinct(_ s: String, _ t: String) -> Int {
if s.count < t.count { return 0 }
if s.count == t.count { return s == t ? 1 : 0 }

let s = Array(s), t = Array(t)
let m = s.count
let n = t.count
var arr = Array(repeating: 0, count: n+1)
arr[0]=1
for i in 1...m {
var pre = 1
for j in 1..<i+m-n+1 {
if j > n { break }
let cur = arr[j]
if s[i-1] == t[j-1] && arr[j-1] != 0 {
arr[j] += pre
}
pre = cur
}
}
return arr[n]
}
}
``````
##### Kotlin
``````class Solution {
fun numDistinct(s: String, t: String): Int {
val lenS = s.length
val lenT = t.length

val dp = Array(lenS + 1) { IntArray(lenT + 1) { idxT -> if (idxT == 0) 1 else 0 } }
for (idxS in 1..lenS) {
for (idxT in 1..lenT) {
dp[idxS][idxT] =
if (s[idxS - 1] == t[idxT - 1]) {
dp[idxS - 1][idxT] + dp[idxS - 1][idxT - 1]
} else {
dp[idxS - 1][idxT]
}
}
}

return dp[lenS][lenT]
}
}
``````