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