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 relative positions of the remaining characters. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

It's 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:

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

Rust Solution

struct Solution;

use std::collections::HashMap;

impl Solution {
    fn num_distinct(s: String, t: String) -> i32 {
        let mut memo: HashMap<(usize, usize), i32> = HashMap::new();
        let s: Vec<char> = s.chars().collect();
        let t: Vec<char> = t.chars().collect();
        let n = s.len();
        let m = t.len();
        Self::dp(0, 0, &mut memo, &s, &t, n, m)
    }

    fn dp(
        i: usize,
        j: usize,
        memo: &mut HashMap<(usize, usize), i32>,
        s: &[char],
        t: &[char],
        n: usize,
        m: usize,
    ) -> i32 {
        if let Some(&res) = memo.get(&(i, j)) {
            return res;
        }
        let res = if j == m {
            1
        } else {
            if i == n {
                0
            } else {
                if s[i] == t[j] {
                    Self::dp(i + 1, j + 1, memo, s, t, n, m) + Self::dp(i + 1, j, memo, s, t, n, m)
                } else {
                    Self::dp(i + 1, j, memo, s, t, n, m)
                }
            }
        };
        memo.insert((i, j), res);
        res
    }
}

#[test]
fn test() {
    let s = "rabbbit".to_string();
    let t = "rabbit".to_string();
    let res = 3;
    assert_eq!(Solution::num_distinct(s, t), res);
    let s = "babgbag".to_string();
    let t = "bag".to_string();
    let res = 5;
    assert_eq!(Solution::num_distinct(s, t), res);
}

Having problems with this solution? Click here to submit an issue on github.