rustgym/leetcode/
_97_interleaving_string.rs

1struct Solution;
2use std::collections::HashMap;
3
4impl Solution {
5    fn is_interleave(s1: String, s2: String, s3: String) -> bool {
6        let n1 = s1.len();
7        let n2 = s2.len();
8        let n3 = s3.len();
9        let s1: Vec<char> = s1.chars().collect();
10        let s2: Vec<char> = s2.chars().collect();
11        let s3: Vec<char> = s3.chars().collect();
12        let mut memo: HashMap<(usize, usize, usize), bool> = HashMap::new();
13        Self::dp(0, 0, 0, &mut memo, &s1, &s2, &s3, n1, n2, n3)
14    }
15
16    fn dp(
17        i: usize,
18        j: usize,
19        k: usize,
20        memo: &mut HashMap<(usize, usize, usize), bool>,
21        s1: &[char],
22        s2: &[char],
23        s3: &[char],
24        n1: usize,
25        n2: usize,
26        n3: usize,
27    ) -> bool {
28        if i == n1 && j == n2 && k == n3 {
29            true
30        } else {
31            if let Some(&res) = memo.get(&(i, j, k)) {
32                return res;
33            }
34            let res = (i < n1
35                && k < n3
36                && s1[i] == s3[k]
37                && Self::dp(i + 1, j, k + 1, memo, s1, s2, s3, n1, n2, n3))
38                || (j < n2
39                    && k < n3
40                    && s2[j] == s3[k]
41                    && Self::dp(i, j + 1, k + 1, memo, s1, s2, s3, n1, n2, n3));
42            memo.insert((i, j, k), res);
43            res
44        }
45    }
46}
47
48#[test]
49fn test() {
50    let s1 = "aabcc".to_string();
51    let s2 = "dbbca".to_string();
52    let s3 = "aadbbcbcac".to_string();
53    let res = true;
54    assert_eq!(Solution::is_interleave(s1, s2, s3), res);
55    let s1 = "aabcc".to_string();
56    let s2 = "dbbca".to_string();
57    let s3 = "aadbbbaccc".to_string();
58    let res = false;
59    assert_eq!(Solution::is_interleave(s1, s2, s3), res);
60}
rustgym/leetcode/_97_interleaving_string.rs

rustgym/leetcode/
_97_interleaving_string.rs
