# 290. Word Pattern

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:

``````Input: pattern = "abba", str = "dog cat cat dog"
Output: true
``````

Example 2:

``````Input:pattern = "abba", str = "dog cat cat fish"
Output: false
``````

Example 3:

``````Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false
``````

Example 4:

``````Input: pattern = "abba", str = "dog dog dog dog"
Output: false
``````

Notes:
You may assume `pattern` contains only lowercase letters, and `str` contains lowercase letters separated by a single space.

Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.

``````class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, string> m;
istringstream in(str);
int i = 0, n = pattern.size();
for (string word; in >> word; ++i) {
if (i >= n) continue;
if (m.count(pattern[i])) {
if (m[pattern[i]] != word) return false;
} else {
for (auto a : m) {
if (a.second == word) return false;
}
m[pattern[i]] = word;
}
}
return i == n;
}
};
``````

``````class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, int> m1;
unordered_map<string, int> m2;
istringstream in(str);
int i = 0, n = pattern.size();
for (string word; in >> word; ++i) {
if (i == n || m1[pattern[i]] != m2[word]) return false;
m1[pattern[i]] = m2[word] = i + 1;
}
return i == n;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/290

Isomorphic Strings

Word Pattern II

https://leetcode.com/problems/word-pattern/

https://leetcode.com/problems/word-pattern/discuss/73402/8-lines-simple-Java