20 lines concise and easy understand C++ solution


  • 0
    A
    unordered_map<char, string> mp;
    unordered_set<string> st;
    bool wordPatternMatch(string pattern, string str) {
        if(pattern.size() == 0) return str.size() == 0;
        if(mp.count(pattern[0])) {
            string value = mp[pattern[0]];
            if(value.size() > str.size() || str.substr(0, value.size()) != value) return false;
            if(wordPatternMatch(pattern.substr(1), str.substr(value.size()))) return true;
        } else {
            for(int i = 1; i <= str.size(); i++){
                if(st.count(str.substr(0, i))) continue;
                mp[pattern[0]] = str.substr(0, i);
                st.insert(str.substr(0, i));
                if(wordPatternMatch(pattern.substr(1), str.substr(i))) return true;
                mp.erase(pattern[0]);
                st.erase(str.substr(0, i));
            }
        }
        return false;
    }

Log in to reply
 

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