C++ accepted solution


  • 0
    J
    bool wordPatternMatch(string pattern, string str) {
        unordered_map<char, string> hmap;
        unordered_set<string> hset;
        return wordPatternMatch(pattern, str, hmap, hset, 0);
    }
    
    bool wordPatternMatch(string pattern, string str, unordered_map<char, string>& hmap, unordered_set<string>& hset, int pos) {
        if(pattern.length() == pos && str.length() == 0)
            return true;
        if(pattern.length() == pos && str.length() != 0 || str.length() == 0 || str.length() < pattern.length() - pos)
            return false;
    
        if(hmap.count(pattern[pos])) {
            string storedPattern = hmap[pattern[pos]];
            int len = storedPattern.length();
            if(str.substr(0, len) != storedPattern)
                return false;
            return wordPatternMatch(pattern, str.substr(len), hmap, hset, pos + 1);
        }
        
        for(int i = 1; i<=str.length(); i++) {
            string t = str.substr(0, i);
            if(hset.count(t))
                continue;
            hmap[pattern[pos]] = t;
            hset.insert(t);
            if(wordPatternMatch(pattern, str.substr(i), hmap, hset, pos + 1))
                return true;
            hmap.erase(pattern[pos]);
            hset.erase(t);
        }
    
        return false;
    }

Log in to reply
 

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