LeetCode Q10: Regular Expression Matching

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:

1. f[i][j] = f[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. f[i][j] = f[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. f[i][j] = f[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

Putting these together, we will have the following code.

	class Solution {
	public:
	bool helper(const string &s, const string &p, int sS, int pS, vector<vector<int> >& f)
	{
	int sSize=s.length();
	int pSize=p.length();
	if(pS==pSize)
	{
	f[sS][pS]=(sS==sSize)? 1:0;
	int tmp=f[sS][pS];
	return f[sS][pS];
	}
	if(p[pS+1]!='*')
	{
	if(sS<sSize && (p[pS]==s[sS] || p[pS]=='.'))
	if(f[sS+1][pS+1]!=-1)
	{
	f[sS][pS]=f[sS+1][pS+1];
	int tmp=f[sS][pS];
	return f[sS][pS];
	}
	else
	{
	f[sS][pS]=helper(s, p, sS+1, pS+1, f);
	int tmp=f[sS][pS];
	return f[sS][pS];
	}
	}
	else
	{
	if(f[sS][pS+2]==-1)
	{
	f[sS][pS]=helper(s, p, sS, pS+2, f);
	int tmp=f[sS][pS];
	if(f[sS][pS]==1)
	return true;
	}
	while(sS<sSize && (p[pS]==s[sS] || p[pS] == '.'))
	{
	if(f[sS+1][pS+2]==-1)
	{
	f[sS][pS]=helper(s, p, sS+1, pS+2, f);
	int tmp=f[sS][pS];
	if(f[sS][pS]==1)
	return true;
	}
	sS++;
	}
	}
	f[sS][pS]=0;
	return false;
	}
	bool isMatch(string s, string p)
	{
	vector<vector<int> > f(s.length()+1, vector<int>(p.length()+1, -1));
	return helper(s, p, 0, 0, f);
	}
	};

view raw Q10DP.cpp hosted with ❤ by GitHub

	class Solution {
	public:
	bool isMatch(string s, string p) {
	/**
	* f[i][j]: if s[0..i-1] matches p[0..j-1]
	* if p[j - 1] != '*'
	* f[i][j] = f[i - 1][j - 1] && s[i - 1] == p[j - 1]
	* if p[j - 1] == '*', denote p[j - 2] with x
	* f[i][j] is true iff any of the following is true
	* 1) "x*" repeats 0 time and matches empty: f[i][j - 2]
	* 2) "x*" repeats >= 1 times and matches "x*x": s[i - 1] == x && f[i - 1][j]
	* '.' matches any single character
	*/
	int m = s.size(), n = p.size();
	vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
	f[0][0] = true;
	for (int i = 1; i <= m; i++)
	f[i][0] = false;
	// p[0.., j - 3, j - 2, j - 1] matches empty iff p[j - 1] is '*' and p[0..j - 3] matches empty
	for (int j = 1; j <= n; j++)
	f[0][j] = j > 1 && '*' == p[j - 1] && f[0][j - 2];
	for (int i = 1; i <= m; i++)
	for (int j = 1; j <= n; j++)
	if (p[j - 1] != '*')
	f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1] || '.' == p[j - 1]);
	else
	// p[0] cannot be '*' so no need to check "j > 1" here
	f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];
	return f[m][n];
	}
	};

view raw q10recursion.cpp hosted with ❤ by GitHub