題目敘述
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 <= 1000s and t consist of English letters.
題目翻譯
題目給定兩個字串 s 和 t，要找出說在 s 中所有可以排列出 t 的總數量。今天參數如果為 s = "rabbbit", t = "rabbit"，那最後會有三種可能。因為 s 可以有三次的操作，來變成 t。
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
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
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]
}
}