regular expression - use dynamic programming

regularexpression_dynamicProgramming.cpp

bool isMatchDP(string s, string p)
{
	int n = s.size();
	int m = p.size();

	vector<bool> prevIsMatch(m + 1, false);
	prevIsMatch[0] = true; // empty string + empty pattern is a match!

	for (int i = 1; i <= m; i++)
	{
		int pi = i - 1;
		if (p[pi] == '*' && prevIsMatch[i - 2])
			prevIsMatch[i] = true;
	}

	for (int i = 1; i <= n; i++)
	{
		vector<bool> curIsMatch(m + 1, false);
		curIsMatch[0] = false; // empty pattern does not match a non-empty string
		for (int j = 1; j <= m; j++)
		{
			int pi = j - 1;
			int si = i - 1;

			if (s[si] == p[pi] || p[pi] == '.')
			{
				curIsMatch[j] = prevIsMatch[j - 1];
			}
			else if (p[pi] == '*')
			{
				bool zeroMatch = curIsMatch[j - 2];
				bool oneMatch = prevIsMatch[j - 2]
&& (s[si] == p[pi - 1] || p[pi - 1] == '.');
				bool onePlusMatch = prevIsMatch[j]
&& (s[si] == p[pi - 1] || p[pi - 1] == '.');
				curIsMatch[j] = zeroMatch || oneMatch || onePlusMatch;
			}
		}

		prevIsMatch.swap(curIsMatch);
	}

	return prevIsMatch[m];
}