# 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.
# Solution
Approach 1: Double hash tables.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char,string> mapP2S;
unordered_map<string,char> mapS2P;
int head = 0;
int tail = 0;
int pIdx = 0;
while (tail <= str.size()) // "<="
{
if (str[head] == ' ')
head++;
else if (str[tail] == ' ' || tail == str.size())
{
string word = str.substr(head, tail - head);
if (mapP2S.find(pattern[pIdx]) != mapP2S.end() &&
mapP2S[pattern[pIdx]] != word)
return false;
if (mapS2P.find(word) != mapS2P.end() &&
mapS2P[word] != pattern[pIdx])
return false;
mapP2S[pattern[pIdx]] = word;
mapS2P[word] = pattern[pIdx];
pIdx++;
head = tail;
}
tail++;
}
return pIdx == pattern.size(); // need to check the length.
}
};