C++ solution based on DFS and pruning.


  • 0
    K

    The following is my answer using DFS and pruning.
    In vec and hmap, the mapping relations between the characters in pattern and the substring in str are recorded.

    class Solution {
    public:
        bool res = false;
        void DFSHelper(string &pattern, int level, string &str, int pos, vector<string> vec, unordered_map<string, char> hmap ) {
            if ( res ) {
                return;
            }
            if ( level == pattern.size() && pos == str.size() ) {
                res = true;
                return;
            }
            if ( level == pattern.size() || pos == str.size() ) {
                return;
            }
            string temp = "";
            while (pos < str.size() ) {
                temp += str[pos++];
                if ( hmap.find(temp) != hmap.end() ) {
                    if ( hmap[temp] != pattern[level] || vec[pattern[level]-'a'] != temp ) {
                        continue;
                    }
                    DFSHelper(pattern, level+1, str, pos,vec,hmap);
                }
                else {
                    if ( vec[pattern[level]-'a'] != "" ) {
                        continue;
                    }
                    vec[pattern[level]-'a'] = temp;
                    hmap[temp] = pattern[level];
                    DFSHelper(pattern, level+1, str, pos,vec,hmap);
                    vec[pattern[level]-'a'] = "";
                    hmap.erase(temp);
                }
            }
        }
        bool wordPatternMatch(string pattern, string str) {
            if ( pattern == "" && str == "" ) {
                return true;
            }
            if ( pattern == "" || str == "" ) {
                return false;
            }
            vector<string> vec(26,"");
            unordered_map<string, char> hmap;
            DFSHelper(pattern, 0, str, 0,vec,hmap );
            return res;
            
        }
    };
    

    WQ@ECE, TAMU


Log in to reply
 

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