291. Word Pattern II

Given a `pattern` and a string `s`, return `true` if `s` matches the `pattern`.

A string `s` matches a `pattern` if there is some bijective mapping of single characters to strings such that if each character in `pattern` is replaced by the string it maps to, then the resulting string is `s`. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

```Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"```

Example 2:

```Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"
```

Example 3:

```Input: pattern = "abab", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "a"
'b' -> "sdasd"
Note that 'a' and 'b' cannot both map to "asd" since the mapping is a bijection.
```

Example 4:

```Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false
```

Constraints:

• `0 <= pattern.length <= 20`
• `0 <= s.length <= 50`
• `pattern` and `s` consist of only lower-case English letters.

291. Word Pattern II
``````struct Solution;
use std::collections::HashSet;

impl Solution {
fn word_pattern_match(pattern: String, s: String) -> bool {
let mut map: Vec<&str> = vec![""; 26];
let mut set: HashSet<&str> = HashSet::new();
let n = pattern.len();
let pattern: Vec<char> = pattern.chars().collect();
Self::dfs(0, &mut map, &mut set, &pattern, &s, n)
}

fn dfs<'a>(
start: usize,
map: &mut Vec<&'a str>,
set: &mut HashSet<&'a str>,
pattern: &[char],
s: &'a str,
n: usize,
) -> bool {
if start == n {
s.is_empty()
} else {
let i = (pattern[start] as u8 - b'a') as usize;
if !map[i].is_empty() {
let size = map[i].len();
if s.starts_with(&map[i]) {
Self::dfs(start + 1, map, set, pattern, &s[size..], n)
} else {
false
}
} else {
let k = s.len();
for size in 1..=k {
let t = &s[..size];
if !set.contains(t) {
map[i] = t;
set.insert(t);
if Self::dfs(start + 1, map, set, pattern, &s[size..], n) {
return true;
}
map[i] = "";
set.remove(t);
}
}
false
}
}
}
}

#[test]
fn test() {
let pattern = "abab".to_string();
let s = "redblueredblue".to_string();
let res = true;
assert_eq!(Solution::word_pattern_match(pattern, s), res);
let pattern = "aaaa".to_string();
let s = "asdasdasdasd".to_string();
let res = true;
assert_eq!(Solution::word_pattern_match(pattern, s), res);
let pattern = "aabb".to_string();
let s = "xyzabcxzyabc".to_string();
let res = false;
assert_eq!(Solution::word_pattern_match(pattern, s), res);
}
``````