# My C++ solution using recursive function call and 2 maps

• ``````class Solution {
bool checkPattern(unordered_map<char, string>& mapping,
unordered_map<string, char>& reverse,
const string &pattern, int pi,
const string &str, int si)
{
if (pi < pattern.size() && si == str.size())
return false;
if (pi == pattern.size() && si == str.size())
return true;
char c = pattern[pi];
if (mapping.find(c) == mapping.end()) {
// enumerate all possible str for this 'c'
size_t max_len = str.size() - si;
for (int l = 1; l <= max_len; l++) {
string prefix = str.substr(si, l);
if (reverse.find(prefix) != reverse.end())
continue;
mapping.insert(make_pair(c, prefix));
reverse.insert(make_pair(prefix, c));
bool next_result = checkPattern(mapping, reverse, pattern, pi+1, str, si + l);
if (next_result) {
return true;
}
mapping.erase(c);
reverse.erase(prefix);
}
}
else {
string prefix = mapping[c];
if (str.substr(si, prefix.size()) == prefix) {
bool next_result = checkPattern(mapping, reverse, pattern, pi+1, str, si + (int)prefix.size());
if (next_result)
return true;
}
}
return false;
}
public:
/**
* Using strategy of solving small piece of problems and then solve large
* problems
*/
bool wordPatternMatch(string pattern, string str) {
unordered_map<char, string> mapping;
unordered_map<string, char> reverse;
bool result = checkPattern(mapping, reverse, pattern, 0, str, 0);
return result;
}
};
``````

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