C++ backtracking


  • 0
    T
    class Solution {
    public:
        bool helper(string pattern, string str, int ip,int is, map<char,pair<string, int> >&mp,set<string>&used){
            //ip: index of p , is: index of str we are looking at
            if(ip==pattern.size()&&is==str.size())return true;
            if(mp.count(pattern[ip])){
                if(mp[pattern[ip]].first==str.substr(is,mp[pattern[ip]].second)){
                    return helper(pattern,str,ip+1,is+mp[pattern[ip]].second,mp,used);
                }
                return false;
            }
            //now it does not exist in mp
            for(int i=is;i<str.size();i++){
                string tmp = str.substr(is,i-is+1);
                if(used.find(tmp)==used.end()){//never mapped to any other char in p
                    mp[pattern[ip]]=make_pair(tmp,tmp.size());
                    used.insert(tmp);
                    bool tmp_ret = helper(pattern,str,ip+1,i+1,mp, used);
                    if(tmp_ret)return true;
                    mp.erase(pattern[ip]);`enter code here`
                    used.erase(tmp);
                }
            }
        }
        bool wordPatternMatch(string pattern, string str) {
            if(pattern.empty()&&str.empty())return true;
            if(pattern.empty()||str.empty()||pattern.size()>str.size())return false;
            map<char,pair<string, int> > mp; //char in p: (sub string in s, size of it)
            set<string>used;//for cases like p=ab and s=aa
            return helper(pattern,str,0,0,mp,used);
        }
    };`enter code here`

Log in to reply
 

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