# My 200ms solution, but very clear in approach!

• class Solution {
public:
set<vector<int>> solSet;
void findSolsBT(vector<vector<int>> &singlePatSize, map<char, int> &patHist,
map<int, char> &charIntID, vector<int> &maxRange,
vector<int> &currSol, int target, int start) {

``````    // If reach the target, add it to solution set.
if (target == 0) {
singlePatSize.push_back(currSol);
solSet.insert(currSol);

// Else increase the size of each variable by 1 and recurse.
} else {
for (int i = start; i < (int)currSol.size(); i++) {
int newTarget = target - patHist[charIntID[i]];

if (currSol[i] < maxRange[i] && newTarget >= 0) {
currSol[i]++;
findSolsBT(singlePatSize, patHist, charIntID, maxRange,
currSol, target - patHist[charIntID[i]], start++);
currSol[i]--;
}
}
}
}

void findSols(vector<vector<int>> &singlePatSize, map<char, int> &patHist,
map<int, char> charIntID, vector<int> &maxRange, int strLen,
int patLen) {

// Initialize the length of string corresponding to every pattern by 1.
vector<int> currSol(patHist.size(), 1);

// Now backtrack to find all possible integer solutions corresponding
// to that equation.
findSolsBT(singlePatSize, patHist, charIntID, maxRange, currSol,
strLen - patLen, 0);
}

bool wordPatternMatch(string pattern, string str) {
bool result = false;

if (pattern.length() > 0 && str.length() > 0
&& pattern.length() <= str.length()) {

// For pattern histogram.
map<char, int> patHist;
map<int, char> charIntID;
map<char, int> intCharID;

// For storing each occurrence location of single character in pattern
map<char, vector<int>> patRep;

int charID = 0;
// Populate the histogram and occurrences.
for (int i = 0; i < (int) pattern.length(); i++) {
if (patHist.find(pattern[i]) == patHist.end()) {
patHist[pattern[i]] = 1;
intCharID[pattern[i]] = charID;
charIntID[charID++] = pattern[i];
} else {
patHist[pattern[i]]++;
}

patRep[pattern[i]].push_back(i);
}

// Figure out the maximum length possible for each character in pattern
vector<int> maxRange(patHist.size(), 1);
for (int i = 0; i < (int) patHist.size(); i++) {
maxRange[i] = (str.length() - pattern.length()
+ patHist[pattern[i]]) / patHist[pattern[i]];
}

// A vector of vector, which stores all possible sizes of strings
// corresponding to each character in pattern.
vector<vector<int>> singlePatSize;

// Find such solutions using back tracking.
findSols(singlePatSize, patHist, charIntID, maxRange, str.length(),
pattern.length());

cout << solSet.size() << endl;
cout << singlePatSize.size() << endl;

// Now check for every pattern if there is possibility.
for (int i = 0; i < (int) singlePatSize.size(); i++) {

// Get corresponding locations in string for each pattern.
vector<int> patLoc(pattern.length(), 0);

// Populate pattern location vector.
for (int j = 1; j < (int) patLoc.size(); j++) {
patLoc[j] = patLoc[j - 1]
+ singlePatSize[i][intCharID[pattern[j - 1]]];
}

// Now check for each pattern in string if it's following the
// rules, else break prematurely.
bool ifCurrPat = true;
string prev = "";

for (int j = 0; j < (int) patRep.size(); j++) {

// Get the first pattern string.
string temp = str.substr(patLoc[patRep[charIntID[j]][0]],
singlePatSize[i][j]);

if (prev == temp) {
ifCurrPat = false;
break;
}

prev = temp;

// If pattern is just occurring once, then no need to check
// it.
if (patRep[charIntID[j]].size() > 1) {

// Now check that pattern if it matches with other
// patterns.
for (int k = 1; k < (int) patRep[charIntID[j]].size();
k++) {

// Break on first mismatch.
if (temp
!= str.substr(
patLoc[patRep[charIntID[j]][k]],
singlePatSize[i][j])) {
ifCurrPat = false;
break;
}
}

// No need to check other patterns as this is not good.
if (!ifCurrPat) {
break;
}
}
}

// Accumulate result for each pattern type, and then just break
// as soon as you observe the correct pattern.
result |= ifCurrPat;
if (result) {
break;
}
}
} else if (pattern.length() == 0 && str.length() == 0) {
result = true;
}

return result;
}
``````

};

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