C++ backtracking using hashset and hashmap


  • 0
    T

    '''
    bool helper(std::string pattern, int ppos, std::string str, int spos, std::unordered_map<char,std::string>& pmap, std::unordered_setstd::string& seen){

        if(ppos == pattern.length() && spos == str.length()){
            return true;
        }
        if(spos == str.length() || ppos == pattern.length())
            return false;
        
        std::string curr;
        for(int i=spos; i<str.length(); ++i){          
            curr += str[spos++];           
            if(seen.find(curr) != seen.end() || (pmap.find(pattern[ppos]) != pmap.end() && !pmap[pattern[ppos]].empty()))
            {
                if(pmap[pattern[ppos]] != curr){
                    continue;
                }
            
                if(helper(pattern,ppos+1,str,spos,pmap,seen))
                    return true;
            }
            else{
                pmap[pattern[ppos]] = curr;
                seen.insert(curr);
                if(helper(pattern,ppos+1,str,spos,pmap,seen))
                    return true;
                seen.erase(curr);
                pmap.erase(pattern[ppos]);  
            }
        
        }
       return false;
    }
    
    bool wordPatternMatch(string pattern, string str) {      
        std::unordered_map<char,std::string> pmap;
        std::unordered_set<std::string> seen;
        return helper(pattern,0,str,0,pmap,seen);
    }
    

    };
    '''


Log in to reply
 

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