44. Wildcard Matching

Problem Statement

Wildcard Matching - LeetCode

Pattern:

---

Solution

Boolean cache[][];
 
public boolean dp (char[] s, char[] p, int i, int j) {
	if(i == s.length && j == p.length) return true;
	if(j == p.length) return i == s.length;
	 
	if(i < s.length && cache[i][j] != null)
		return cache[i][j];
	
	if(i < s.length && (s[i] == p[j] || p[j] == '?')) 
		return cache[i][j] = dp(s, p, i+1, j+1);
	
	if(p[j] == '*') return cache[i][j] = 
		i < s.length ? (
			dp(s, p, i+1, j+1) ||   // advance both   OR
			dp(s, p, i+1, j) ||     // advance string OR
			dp(s, p, i, j+1)        // advance pattern
			) : dp(s, p, i, j+1);   // advance pattern only       
	
	return cache[i][j] = false;
}
 
public boolean isMatch(String s, String p) {
	if(s.length() == 0 && p.length() == 0) return true;
	if (s.length()==0) {
		for (char ch : p.toCharArray()) if(ch!='*') return false;
		return true;
	}
	cache = new Boolean[s.length()+1][p.length()+1];
	return dp(s.toCharArray(), p.toCharArray(), 0, 0);
}

TC : $O(n\ast m)$ SC : $O(n\ast m)$

Notes

• Match both strings from start to finish
  • if s[i]==p[j] or p[j == '?' then increment both
  • else if p[j] == '*'
    • then there can be 3 cases
      • match * with s[i] and increment both
      • include s[i] in * string and increment s[i]
      • take * as empty string and increment only p[j]
    • but if i == s.length we can only increment the pattern p[j]
      • this will be the case if the asterisk is in the end s = abac p = abac*****