# DFS with Memoization (DP)

• 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);
}
};``````

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