Leetcode 290. Word Pattern

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Solution

class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<string, char> m;
unordered_map<char, string> n;
// tokenizer
stringstream input(s);
string token;
vector<string> words;
while (getline(input, token, ' ')) {
words.push_back(token);
}

if (pattern.length() != words.size())
return false;

for(int i=0; i<pattern.length(); i++) {
if (n.find(pattern[i]) == n.end()) {
if (m.find(words[i]) == m.end()) {
m[words[i]] = pattern[i];
n[pattern[i]] = words[i];
} else if (m[words[i]] != pattern[i]){
return false;
}
} else {
if (n[pattern[i]] != words[i]) {
return false;
}
}
}
return true;
}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store