C++ Map & Set Backtrail approach.


  • 0
    L

    The difficulty is to verify pattern match from both two ways, pattern -> string (using map), string is exclusive assign to a pattern (using set).

    bool dfs(string& pattern, string& str, int m, int n, unordered_map<char, string>& dict, unordered_set<string>& words, int p, int s){
            if(p == m && s == n){
                return true;
            }else if(p == m || s == n){
                return false;
            }
            
            char curPattern = pattern[p];
            if(dict.find(curPattern) != dict.end()){
                string word = dict[curPattern];
                if(s + word.size() <= n && word == str.substr(s, word.size())){
                    return dfs(pattern, str, m, n, dict, words, p+1, s + word.size());
                }
                return false;
            }
            
            for(int i = s+1; i <= n; i++){
                string newWord = str.substr(s, i - s);
                if(words.find(newWord) != words.end()){
                    continue;
                }
                
                dict[curPattern] = newWord;
                words.insert(newWord);
                
                if(dfs(pattern, str, m, n, dict, words, p+1, i)){
                    return true;
                }
                
                dict.erase(curPattern);
                words.erase(newWord);
            }
            
            return false;
        }
    
        bool wordPatternMatch(string pattern, string str) {
            int m = pattern.size(), n = str.size();
            
            unordered_map<char, string> dict;
            unordered_set<string> words;
            return dfs(pattern, str, m, n, dict, words, 0, 0);
        }
    

Log in to reply
 

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