My C++ solution using recursive function call and 2 maps


  • 0
    B
    class Solution {
        bool checkPattern(unordered_map<char, string>& mapping,
                          unordered_map<string, char>& reverse,
                          const string &pattern, int pi,
                          const string &str, int si)
        {
            if (pi < pattern.size() && si == str.size())
                return false;
            if (pi == pattern.size() && si == str.size())
                return true;
            char c = pattern[pi];
            if (mapping.find(c) == mapping.end()) {
                // enumerate all possible str for this 'c'
                size_t max_len = str.size() - si;
                for (int l = 1; l <= max_len; l++) {
                    string prefix = str.substr(si, l);
                    if (reverse.find(prefix) != reverse.end())
                        continue;
                    mapping.insert(make_pair(c, prefix));
                    reverse.insert(make_pair(prefix, c));
                    bool next_result = checkPattern(mapping, reverse, pattern, pi+1, str, si + l);
                    if (next_result) {
                        return true;
                    }
                    mapping.erase(c);
                    reverse.erase(prefix);
                }
            }
            else {
                string prefix = mapping[c];
                if (str.substr(si, prefix.size()) == prefix) {
                    bool next_result = checkPattern(mapping, reverse, pattern, pi+1, str, si + (int)prefix.size());
                    if (next_result)
                        return true;
                }
            }
            return false;
        }
    public:
        /**
         * Using strategy of solving small piece of problems and then solve large
         * problems
         */
        bool wordPatternMatch(string pattern, string str) {
            unordered_map<char, string> mapping;
            unordered_map<string, char> reverse;
            bool result = checkPattern(mapping, reverse, pattern, 0, str, 0);
            return result;
        }
    };
    

Log in to reply
 

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