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.

題目翻譯

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

rabbbit
..x
rabbbit
...x
rabbbit
....x

解法解析

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

當 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

/**
 * @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]
    }
}