Leetcode 44: Wildcard Matcher

class Solution {
public:
    bool isMatch(string s, string p) {
        // handle the easy corner case
        if (p == "") return s == "";

        Node* automaton = buildAutomaton(p);
        
        // use a hash map to keep track of calculation when we go throug the search
        map< pair<int,int>, bool > dp;
        return matchPattern(s, 0, automaton, dp);
    }
    
    
    struct Node {
        bool isAny;         // mark if this node is redirected by '*'
                            // note that when we find a '*', we do not create a new node
        bool isSingle;      // mark if this node is created by '?'
        bool isStart;       // mark the node as the start node. This seems to be redundant
        bool isEnd;         // makr the node as termination node
        char code;          // only when the character matches the code, we can move to next node
        int  remaining;     // the minimum number that we need to satisfy the remaining pattern node chain
        int id;             // id of the node. This is one of the key used in the hash map
        Node* next;         // pointer to the next node
        Node() : isAny(false), isSingle(false), isStart(false), isEnd(false), code('\0'), next(nullptr), id(0), remaining(0) {};
    };
    
    Node* buildAutomaton(string& s) {
        Node* start_node = new Node();
        start_node->isStart = true;
        start_node->id = 0;
        int count = 0;
        for (char c : s) if (c != '*') ++count;
        start_node->remaining = count;
        
        // start with start_node, which is also returned by the function
        Node* curr = start_node;
        
        for (int i = 0; i < s.size(); ++i) {
            char ch = s[i];
            
            if (ch == '*') {
                curr->isAny = true; // note that we do not move to the next node
            } else if (ch == '?') {
                curr->isSingle = true;
                Node* new_node = new Node();
                new_node->id = curr->id + 1;
                new_node->remaining = curr->remaining - 1;
                curr->next = new_node;
                curr = new_node;
            } else {
                Node* new_node = new Node();
                curr->code = ch;
                curr->next = new_node;
                new_node->id = curr->id + 1;
                new_node->remaining = curr->remaining - 1;
                curr = new_node;
            }
        }
        
        // mark the current node as the end node
        curr->isEnd = true;
        return start_node;
    }
    
    bool matchPattern(string& s, int level, Node* node, map<pair<int,int>, bool>& dp) {
        /*
        cout << "level: " << level << ", id: " << node->id << ", remaining: " << node->remaining << endl;
        cout << "isAny: " << (node->isAny ? "true" : "false") << endl;
        cout << "isSingle: " << (node->isSingle ? "true" : "false" ) << endl;
        cout << "isEnd: " << (node->isEnd ? "true" : "false") << endl; 
        //*/
        
        // if we have already met this situation, return the calculation result directly
        if (dp.find(make_pair(level, node->id)) != dp.end()) return dp[make_pair(level, node->id)];
        
        // this case, the pattern is '*', which match all the string.
        if (node->isStart && node->isEnd) return true;
        
        // if we arrive at end node, we check
        // (1) if we arrive at the end of the string
        // (2) if we are at '*'. In this case, the last character in the pattern string is '*'
        //     which matches all the remaining string
        // (3) otherwise, we have a mismatch
        if (node->isEnd) {
            if (level == s.size()) {
                return true;
            } else if (node->isAny) {
                return true;
            } else {
                return false;
            }
   
        }
        
        // if we arrive at the end of hte string, check if we arrive at the end of pattern string
        if (level == s.size()) return (node->isEnd);
        
        pair<int,int> mypair{level, node->id};
        
        // prune the search space
        if (level + node->remaining > s.size()) {
            dp[mypair] = false;
            return dp[mypair];
        }
        
        
        // the order of test is important. We need to test if the node is '*' first
        // because it may be possible that a node is '*' and '?' at the same time.
        if (node->isAny) {
            if (node->code == s[level] || node->isSingle) {
                dp[mypair] = matchPattern(s, level+1, node->next, dp) || matchPattern(s, level+1, node, dp);
            } else {
                dp[mypair] = matchPattern(s, level+1, node, dp);
            }
        } else if (node->isSingle) {    
            dp[mypair] = matchPattern(s, level+1, node->next, dp);
        } else {
            dp[mypair] = (node->code == s[level] && matchPattern(s, level+1, node->next, dp));
        }
        
        return dp[mypair];
    }
    
    

};