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.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);
}