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.