87. Scramble String Hard

1/**
2 * [87] Scramble String
3 *
4 * We can scramble a string s to get a string t using the following algorithm:
5 * <ol>
6 * If the length of the string is 1, stop.
7 * If the length of the string is > 1, do the following:
8 *
9 * Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
10 * Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
11 * Apply step 1 recursively on each of the two substrings x and y.
12 *
13 *
14 * </ol>
15 * Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.
16 *  
17 * Example 1:
18 *
19 * Input: s1 = "great", s2 = "rgeat"
20 * Output: true
21 * Explanation: One possible scenario applied on s1 is:
22 * "great" --> "gr/eat" // divide at random index.
23 * "gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
24 * "gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
25 * "g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
26 * "r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
27 * "r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
28 * The algorithm stops now, and the result string is "rgeat" which is s2.
29 * As one possible scenario led s1 to be scrambled to s2, we return true.
30 *
31 * Example 2:
32 *
33 * Input: s1 = "abcde", s2 = "caebd"
34 * Output: false
35 *
36 * Example 3:
37 *
38 * Input: s1 = "a", s2 = "a"
39 * Output: true
40 *
41 *  
42 * Constraints:
43 *
44 * s1.length == s2.length
45 * 1 <= s1.length <= 30
46 * s1 and s2 consist of lowercase English letters.
47 *
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/scramble-string/
52// discuss: https://leetcode.com/problems/scramble-string/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55use std::collections::HashMap;
56
57impl Solution {
58    pub fn is_scramble(s1: String, s2: String) -> bool {
59        let mut mem = HashMap::new();
60        return Self::_is_scramble(&s1, &s2, &mut mem);
61    }
62
63    fn _is_scramble<'a>(
64        s1: &'a str,
65        s2: &'a str,
66        map: &mut HashMap<(&'a str, &'a str), bool>,
67    ) -> bool {
68        if let Some(x) = map.get(&(s1, s2)) {
69            return *x;
70        }
71
72        if s1.len() != s2.len() {
73            map.insert((s1, s2), false);
74            return false;
75        }
76
77        if s1 == s2 {
78            map.insert((s1, s2), true);
79            return true;
80        }
81
82        let mut chs = vec![0; 26];
83        for c in s1.chars() {
84            chs[c as usize - 'a' as usize] += 1;
85        }
86        for c in s2.chars() {
87            chs[c as usize - 'a' as usize] -= 1;
88        }
89        for c in chs.iter() {
90            if *c != 0 {
91                map.insert((s1, s2), false);
92                return false;
93            }
94        }
95        for i in 1..s1.len() {
96            if Self::_is_scramble(&s1[..i], &s2[..i], map)
97                && Self::_is_scramble(&s1[i..], &s2[i..], map)
98            {
99                map.insert((s1, s2), true);
100                return true;
101            }
102            if Self::_is_scramble(&s1[..i], &s2[s2.len() - i..], map)
103                && Self::_is_scramble(&s1[i..], &s2[..s2.len() - i], map)
104            {
105                map.insert((s1, s2), true);
106                return true;
107            }
108        }
109        map.insert((s1, s2), false);
110        false
111    }
112}
113
114// submission codes end
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119
120    #[test]
121    fn test_87() {
122        assert_eq!(
123            Solution::is_scramble("great".to_owned(), "rgeat".to_owned()),
124            true
125        );
126        assert_eq!(
127            Solution::is_scramble("abcde".to_owned(), "caebd".to_owned()),
128            false
129        );
130        assert_eq!(
131            Solution::is_scramble("abb".to_owned(), "bba".to_owned()),
132            true
133        );
134    }
135
136    #[test]
137    fn test_87_2() {
138        assert_eq!(
139            Solution::is_scramble(
140                "eebaacbcbcadaaedceaaacadccd".to_owned(),
141                "eadcaacabaddaceacbceaabeccd".to_owned()
142            ),
143            false
144        );
145    }
146}
147