word-pattern

Word Pattern – LeetCode 290

Problem

Description

Given a pattern and a string str, find if str 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 str.

Example

1. pattern = “abba”, str = “dog cat cat dog” should return true.
2. pattern = “abba”, str = “dog cat cat fish” should return false.
3. pattern = “aaaa”, str = “dog cat cat dog” should return false.
4. pattern = “abba”, str = “dog dog dog dog” should return false.

Answer

Original

Code

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, string> m;
        istringstream in(str);
        unsigned i = 0;
        for (string word; in >> word; ++i) {
            if (m.find(pattern[i]) != m.end()) {
                if (m[pattern[i]] != word) return false;
            } else {
                for (unordered_map<char, string>::iterator it = m.begin(); it != m.end(); ++it) {
                    if (it->second == word) return false;
                }
                m[pattern[i]] = word;
            }
        }
        return i == pattern.size();
    }
};

思路

简单的建立map去查表，但要注意反查的过程，时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$3$ ms，排名$66.67\%$

Better

思路

还没看到更好的思路。