290. Word Pattern

1. 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.

2. Example

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

3. 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.

4. Solutions

My Accepted Solution

n = i_pattern.size(), m = i_str.size()
Time complexity: O(n)
Space complexity: O(m)

class Solution {
public:
    bool wordPattern(const string &pattern, const string &str) {
        unordered_map<char, string> to_string;
        unordered_map<string, char> to_letter;

        stringstream stream(str);
        string word;
        for (int i = 0; i < pattern.size(); ++i) {
            if (!(stream >> word)) {
                return false;
            }

            if (to_string.find(pattern[i]) != to_string.end() && to_string[pattern[i]] != word ||
                to_letter.find(word) != to_letter.end() && to_letter[word] != pattern[i]) {
                return false;
            }

            to_string[pattern[i]] = word;
            to_letter[word] = pattern[i];
        }

        return !(stream >> word);
    }
};