# LeetCode Solution, Hard, 115. Distinct Subsequences

# [115. Distinct Subsequences](https://leetcode.com/problems/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.

#### 題目翻譯

題目給定兩個字串 `s` 和 `t`，要找出說在 `s` 中所有可以排列出 `t` 的總數量。今天參數如果為 `s = "rabbbit"`, `t = "rabbit"`，那最後會有三種可能。因為 `s` 可以有三次的操作，來變成 `t`。

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

### 解法解析

這題很明顯的就是使用 Dynamic programming 的方式來求解。下方會附上兩個我覺得不錯的講解。這邊簡單提解題思維。主要是使用一個二維的陣列，去計算說在 `s[j]` 的時候有幾個 `t[i]` 的可能。以下是範例圖：

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

當 s[6] 和 t[3] 的時候，代表 `rab` 在 `rabbi` 中有三種組合的意思。當 `s[i-1] != t[j-1]` 的時候，相當於在 `s[i-1]` 的數量，所以是 `dp[i][j] = dp[i-1][j]`。在 `s[i-1] == t[j-1]` 時，`dp[i][j] = dp[i-1][j] + dp[i-1][j-1]`。

- https://www.youtube.com/watch?v=mPqqXh8XvWY
- https://leetcode.com/problems/distinct-subsequences/discuss/229775/a-foolish-solution-by-golang-GO-4ms-DP-100

#### 程式範例

##### Python

```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

```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

```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

```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

```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]
    }
}
```