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. Specifically:

• Each letter in pattern maps to exactly one unique word in s.
• Each unique word in s maps to exactly one letter in pattern.
• No two letters map to the same word, and no two words map to the same letter.

2. Example

Example 1

Input: pattern = “abba”, s = “dog cat cat dog”
Output: true
Explanation:
The bijection can be established as:

• ‘a’ maps to “dog”.
• ‘b’ maps to “cat”.

Example 2

Input: pattern = “abba”, s = “dog cat cat fish”
Output: false

Example 3

Input: pattern = “aaaa”, s = “dog cat cat 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

Hash Table

m = pattern.size(), n = s.size()
Time complexity: O(m + n)
Space complexity: O(m + n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    bool wordPattern(const string &pattern, const string &s) {
        const int n = pattern.size();
        stringstream stream(s);
        unordered_map<char, string> pattern_to_s;
        unordered_map<string, char> s_to_pattern;
        for (int i = 0; i < n; ++i) {
            if (stream.eof()) {
                return false;
            }

            char letter = pattern[i];
            string str;
            stream >> str;

            if (pattern_to_s.find(letter) == pattern_to_s.end() &&
                s_to_pattern.find(str) == s_to_pattern.end()) {
                pattern_to_s[letter] = str;
                s_to_pattern[str] = letter;
            } else if (pattern_to_s[letter] != str || s_to_pattern[str] != letter) {
                return false;
            }
        }

        return stream.eof();
    }
};