# Word Pattern 1 & 2 & 3

• Word Pattern 1 --------- 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.

``````
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, int> char2pos;
unordered_map<string, int> str2pos;
istringstream in(str);
int i = 0;
for (string word; in >> word; i++) {
//pattern or word have existed previously, check whether equal
if (char2pos.find(pattern[i]) != char2pos.end() || str2pos.find(word) != str2pos.end()) {
if (char2pos[pattern[i]] != str2pos[word]) return false;
}
//pattern & word add to the map
else {
char2pos[pattern[i]] = str2pos[word] = i + 1;
}
}
return i == pattern.size();
}
};

``````

Now let us look at the template solution for the Word Pattern 1&2

``````
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, string> char2str;
unordered_set<string> dict;
istringstream in(str);
int i = 0;
for (string word; in >> word; i++) {
if (char2str.find(pattern[i]) != char2str.end()) {
if (char2str[pattern[i]] != word) return false;
} else {
if (dict.find(word) != dict.end()) return false;
char2str[pattern[i]] = word;
}
dict.insert(word);
}
return i == pattern.size();
}
};
``````
``````class Solution {
unordered_set<string> str;
unordered_map<char, string> pat2str;
public:
bool wordPatternMatch(string pattern, string str) {
return dfs(str, 0, pattern, 0);
}
private:
bool dfs(string& str, int pos_str, string& pat, int pos_pat) {
if (pos_str == str.size() && pos_pat == pat.size()) return true;
if (pos_str == str.size() || pos_pat == pat.size()) return false;
char ch = pattern[p];
for (int i = pos_str; i < str.size(); i++) {
string cur = str.substr(pos_str, i - pos_str + 1);
//char ch and the cur string both exist previously
if (pat2str.count(ch) && pat2str[ch] == cur) {
if (dfs(str, i + 1, pat, pos_pat + 1)) return true;
}
//char ch not exist before, check whether the cur exist previously
else if (!pat2str.count(ch)) {
//current string exists previosly, so continue !
if (str.count(cur)) continue;
//not exist before, just add it
pat2str[ch] = cur;
str.insert(cur);
if (dfs(str, i + 1, pat, pos_pat + 1)) return true;
pat2str.erase(ch);
str.erase(cur);
}
}
return false;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.