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

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.

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, int> m1;
        unordered_map<string, int> m2;

        stringstream ss(s);
        int i = 0;
        int n = pattern.size();
        for (string word; ss >> word; ++i) {
            // 如果遇到 i == n 的情況，代表 pattern 已經先到終點了
            // 但 word 還有單字
            if (i == n || m1[pattern[i]] != m2[word]) {
                return false;
            }
            // 更新 index + 1
            m1[pattern[i]] = i + 1;
            m2[word] = i + 1;
        }
        // 最後比較 i 有沒有到達終點
        return i == n;
    }
};

• T: $O(n + m)$
• S: $O(n)$