115. Distinct Subsequences Hard

1/**
2 * [115] Distinct Subsequences
3 *
4 * Given two strings s and t, return the number of distinct subsequences of s which equals t.
5 * 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).
6 * The test cases are generated so that the answer fits on a 32-bit signed integer.
7 *  
8 * Example 1:
9 * 
10 * Input: s = "rabbbit", t = "rabbit"
11 * Output: 3
12 * Explanation:
13 * As shown below, there are 3 ways you can generate "rabbit" from s.
14 * <u>rabb</u>b<u>it</u>
15 * <u>ra</u>b<u>bbit</u>
16 * <u>rab</u>b<u>bit</u>
17 * 
18 * Example 2:
19 * 
20 * Input: s = "babgbag", t = "bag"
21 * Output: 5
22 * Explanation:
23 * As shown below, there are 5 ways you can generate "bag" from s.
24 * <u>ba</u>b<u>g</u>bag
25 * <u>ba</u>bgba<u>g</u>
26 * <u>b</u>abgb<u>ag</u>
27 * ba<u>b</u>gb<u>ag</u>
28 * babg<u>bag</u>
29 *  
30 * Constraints:
31 * 
32 * 	1 <= s.length, t.length <= 1000
33 * 	s and t consist of English letters.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/distinct-subsequences/
39// discuss: https://leetcode.com/problems/distinct-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn num_distinct(s: String, t: String) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_115() {
57    }
58}
59