My 200ms solution, but very clear in approach!


  • 0
    G

    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;
    }
    

    };


Log in to reply
 

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