LeetCode Q44: Wildcard Matching

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

I implement a DP solution, but the code didn't pass all test cases of leetcode due to running over the memory limit of leetcode.

My code is given as below:

	bool helper(string s, string p, vector<vector<int> >& flag){
	if(flag[s.length()][p.length()]!=-1)
	return flag[s.length()][p.length()];
	if(s[0]==p[0]||p[0]=='?'){
	return flag[s.length()-1][p.length()-1];
	}
	if(p[0]=='*'){
	bool r0=false;
	bool r1=false;
	bool r2=false;
	r0=flag[s.length()][p.length()-1];
	if(r0==true){
	flag[s.length()][p.length()]=r0;
	return r0;
	}
	r1=flag[s.length()-1][p.length()];
	if(r1==true){
	flag[s.length()][p.length()]=r1;
	return r1;
	}
	r2=flag[s.length()-1][p.length()-1];
	if(r2==true){
	flag[s.length()][p.length()]=r2;
	return r2;
	}
	flag[s.length()][p.length()]=false;
	return false;
	}
	if(s[0]!=p[0]&&p[0]!='*'&&p[0]!='?')
	flag[s.length()][p.length()]=0;
	return flag[s.length()][p.length()];
	}
	bool isMatch(string s, string p) {
	vector<vector<int> > flag(s.length()+1, vector<int>(p.length()+1, -1));
	flag[0][0]=1;
	for(int j=1; j<=p.length(); ++j)
	flag[0][j]=flag[0][j-1]&&(p[p.length()-j]=='?'||p[p.length()-j]=='*');
	for(int i=1; i<=s.length(); ++i)
	flag[i][0]=0;
	bool r=helper(s, p, flag);
	return r;
	}

view raw Q44WildcardMatching1.cpp hosted with ❤ by GitHub

This question can actually be solved using greedy algorithm which takes only O(s.length()+p.length()) time and constant space. For exact solution please refer to leetcode forum at:
https://leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution.

The method, try to match as many common characters of s and p, and when match is failed at current location, it roll back and to last '*' location, and increment pointer of s by one. It will roll back again and make the increment if the match still can not be found.

For each element in s
If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
If p=='*', this is also a match, but one or many chars may be available, so let us save this *'s position and the matched s position.
If not match, then we check if there is a * previously showed up,
       if there is no *,  return false;
       if there is an *,  we set current p to the next element of *, and set current s to the next saved s position.

For quick reference, the code is given in below:

	class Solution {
	public:
	bool isMatch(string s, string p) {
	int m = s.length(), n = p.length();
	int i = 0, j = 0, asterick = -1, match;
	while (i < m) {
	if (j < n && p[j] == '*') {
	match = i;
	asterick = j++;
	}
	else if (j < n && (s[i] == p[j] || p[j] == '?')) {
	i++;
	j++;
	}
	else if (asterick >= 0) {
	i = ++match;
	j = asterick + 1;
	}
	else return false;
	}
	while (j < n && p[j] == '*') j++;
	return j == n;
	}
	};

view raw Q44WildcardMatching2.cpp hosted with ❤ by GitHub