12ms solution using C++, back tracing with pruning


  • 1
    T
    class Solution {
    private:
        //for prune
        vector<int> hist;
        int lowerBound;
        
        bool dfs(string &pattern, int pStep, string &str, int sStep, unordered_map<char, string> &mp, unordered_set<string> &st){
            if(pStep == pattern.length() || sStep == str.length()){
                if(pStep == pattern.length() && sStep == str.length())
                    return true;
                else
                    return false;
            }
            
            int sLength = str.length(), pLength = pattern.length();
            //for prune
            if(sLength - sStep < lowerBound)
                return false;
            if(mp.find(pattern[pStep]) == mp.end()){
                for(int len = 1; sStep + len <= sLength; ++len){
                    string token = str.substr(sStep, len);
                    if(st.find(token) == st.end()){
                        mp[pattern[pStep]] = token;
                        st.insert(token);
                        lowerBound += (hist[pattern[pStep] - 'a'] * (len - 1) - len);//for prune
                        if(dfs(pattern, pStep + 1, str, sStep + len, mp, st))
                            return true;
                        lowerBound -= (hist[pattern[pStep] - 'a'] * (len - 1) - len);//for prune
                        st.erase(token);
                        mp.erase(pattern[pStep]);
                    }
                }
            }
            else{
                string token = mp[pattern[pStep]];
                if(sStep + token.length() <= sLength && str.substr(sStep, token.length()) == token){
                    lowerBound -= token.length(); //for prune
                    if(dfs(pattern, pStep + 1, str, sStep + token.length(), mp, st))
                        return true;
                    lowerBound += token.length(); //for prune
                }
            }
            return false;
        }
        
    public:
        bool wordPatternMatch(string pattern, string str) {
            unordered_map<char, string> mp;
            unordered_set<string> st;
            hist.resize(26, 0);
            for(auto c : pattern)
                ++hist[c - 'a'];
            lowerBound = pattern.length();
            return dfs(pattern, 0, str, 0, mp, st);
        }
    };

  • 0
    Y

    the idea of early prune is very great. Though a little bit complex.


Log in to reply
 

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