DFS with Memoization (DP)


  • 0
    H

    The matching is simple. The base case is when the pattern string p is empty. If s is also empty, then return true; otherwise false. Based on this, every time we match the current first unit in p. There are two possibilities: 1) a single character, either a normal char or '.'; 2) a character followed by '*'. For the first case, we match the first character and then match the rest recursively. For the second case, we enumerate all possible positions we can match in string s, and match the rest recursively. To avoid duplicate computation, we use a hash table to store the matching result.

    // s = "abc"  c='.'     --> 0,1,2,3
    // s = "aabb" c='a'   --> 0,1,2
    vector<int> match_idx(string s, char c) {
        vector<int> res;
        res.push_back(0);
        // find out all possible positions to match the first substring
        for (int i = 0; i < s.length(); i ++)
            if (c == '.' || s[i] == c)
                res.push_back(i+1);
            else
                break;
        return res;
    }
    
    bool DFS(string s, string p, unordered_map<string,bool>& bmatch) {
            string key = s + "+" + p;
            if (bmatch.find(key) != bmatch.end())
                return bmatch[key];
            // base case
            if (p.length() == 0) {
                if (s.length() == 0)
                    return true;
                else
                    return false;
            }
            bool ret = false;
            // case by case
            if (p.length()>1 && p[1] == '*') {
                vector<int> idx = match_idx(s, p[0]);
                for (int i = 0; i < idx.size(); i ++)
                    if (DFS(s.substr(idx[i]), p.substr(2), bmatch)) {
                        ret = true;
                        break;
                    }
            }
            else if (s.length()>0 && (p[0] == '.' || p[0] == s[0]))
                ret = DFS(s.substr(1), p.substr(1), bmatch);
                
            bmatch[key] = ret;
            return ret;
    }
    
    class Solution {
    public:
        bool isMatch(string s, string p) {
            unordered_map<string, bool> bmatch;
            return DFS(s, p, bmatch);
        }
    };

Log in to reply
 

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