LeetCode 290. Word Pattern

[quinnwencn]

Description

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

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

[quinnwencn]

Analysis

The difference between this problem and Leetcode 205 is that one string changed to words. So we can not use array to remember the sequence anymore. But we can use hash map to remember the index of first occurrence of letter and words.

Solution written in Cpp

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        stringstream ss {s};
        vector<string> words;
        string word;
        while (ss >> word) {
            words.push_back(word);
        }

        if (words.size() != pattern.length()) {
            return false;
        }

        std::unordered_map<char, int> charPattern;
        std::unordered_map<string, int> sPattern;
        for (auto i = 0; i < words.size(); ++i) {
            if (charPattern.contains(pattern[i]) && sPattern.contains(words[i]) && charPattern[pattern[i]] == sPattern[words[i]]) {
                continue;
            } else if (!charPattern.contains(pattern[i]) && !sPattern.contains(words[i])) {
                charPattern[pattern[i]] = i;
                sPattern[words[i]] = i;
            } else {
                return false;
            }
        }

        return true;
    }
};

Solution written inRust

impl Solution {
    pub fn word_pattern(pattern: String, s: String) -> bool {
        let items: Vec<&str> = s.split(" ").collect();
        if items.len() != pattern.len() {
            return false;
        }
        let mut pattern_hash: std::collections::HashMap<char, i32> = std::collections::HashMap::new();
        let mut word_hash: std::collections::HashMap<&str, i32> = std::collections::HashMap::new();
        let iter = pattern.chars().zip(items.iter());
        let mut index = 0;
        for (c, word) in iter {
            index += 1;
            if (pattern_hash.contains_key(&c) && word_hash.contains_key(word) && pattern_hash[&c] == word_hash[word]) {
                continue;
            } else if !pattern_hash.contains_key(&c) && !word_hash.contains_key(word) {
                pattern_hash.insert(c, index);
                word_hash.insert(word, index);
            } else {
                return false;
            }
        }

        true
    }
}