290. Word Pattern
Given a pattern
and a string s
, find if s
follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern
and a non-empty word in s
.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog" Output: true
Example 2:
Input: pattern = "abba", s = "dog cat cat fish" Output: false
Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog" Output: false
Example 4:
Input: pattern = "abba", s = "dog dog dog dog" Output: false
Constraints:
1 <= pattern.length <= 300
pattern
contains only lower-case English letters.1 <= s.length <= 3000
s
contains only lower-case English letters and spaces' '
.s
does not contain any leading or trailing spaces.- All the words in
s
are separated by a single space.
Rust Solution
struct Solution;
use std::collections::HashMap;
impl Solution {
fn word_pattern(pattern: String, string: String) -> bool {
let chars: Vec<char> = pattern.chars().collect();
let strings: Vec<String> = string.split_whitespace().map(|s| s.to_string()).collect();
if chars.len() != strings.len() {
return false;
}
let mut hm1: HashMap<char, String> = HashMap::new();
let mut hm2: HashMap<String, char> = HashMap::new();
for i in 0..chars.len() {
let ch = chars[i];
let string = strings[i].clone();
if let Some(s) = hm1.get(&ch) {
if *s != string {
return false;
}
} else {
hm1.insert(ch, string.clone());
}
if let Some(c) = hm2.get(&string) {
if *c != ch {
return false;
}
} else {
hm2.insert(string.clone(), ch);
}
}
true
}
}
#[test]
fn test() {
assert_eq!(
Solution::word_pattern("abba".to_string(), "dog cat cat dog".to_string()),
true
);
assert_eq!(
Solution::word_pattern("abba".to_string(), "dog cat cat fish".to_string()),
false
);
assert_eq!(
Solution::word_pattern("aaaa".to_string(), "dog cat cat dog".to_string()),
false
);
assert_eq!(
Solution::word_pattern("abba".to_string(), "dog dog dog dog".to_string()),
false
);
}
Having problems with this solution? Click here to submit an issue on github.