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.
Solution
We use two unordered_map to form a one-to-one mapping for characters in pattern and the words in s to match the pattern.
Implementation
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
29
30
31
32
class Solution {
public:
bool wordPattern(string pattern, string s) {
vector<string> split;
string delimiter = " ";
size_t pos = 0;
while ((pos = s.find(delimiter)) != string::npos) {
string str = s.substr(0, pos);
split.push_back(str);
s.erase(0, pos + delimiter.length());
}
split.push_back(s);
if (split.size() != pattern.length()) return false;
unordered_map<char, string> hashMap;
unordered_map<string, char> rHashMap;
for (int i = 0; i < pattern.length(); i++) {
char cur = pattern[i];
if (hashMap.find(cur) == hashMap.end() &&
rHashMap.find(split[i]) == rHashMap.end()) {
hashMap[cur] = split[i];
rHashMap[split[i]] = cur;
}
else {
if (hashMap[cur] != split[i] || rHashMap[split[i]] != cur) return false;
}
}
return true;
}
};
Here is another solution using stringstream to get the words from s a bit easier.
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
class Solution {
public:
bool wordPattern(string pattern, string s) {
stringstream ss(s);
unordered_map<char, string> patternToStr;
unordered_map<string, char> strToPattern;
string temp;
size_t count = 0;
while (ss >> temp) {
char c = pattern[count];
if (patternToStr.find(c) == patternToStr.end() &&
strToPattern.find(temp) == strToPattern.end()) {
patternToStr[c] = temp;
strToPattern[temp] = c;
}
else {
if (patternToStr[c] != temp || strToPattern[temp] != c) return false;
}
count++;
}
return count == pattern.length();
}
};