Regular Expression Matching(LeetCode)

| Tags LeetCode  Algorithm 
#include <iostream>
#include <string>

using namespace std;

bool isMatch(const char *s, const char *p)
{
	if(p[0] == '*')
		return false;
	else if(p[0] == 0)
		return s[0] == 0;
	else if(p[0] == '.')
	{
		if(p[1] == '*')
		{
			if(p[2] == 0)
				return true;

			if(isMatch(s, p+2))
				return true;

			for(const char *snext = s; ; ++snext)
			{
				if(snext[0] == 0)
					return false;
				if(isMatch(snext+1, p+2))
					return true;
			}
		}
		else
		{
			return s[0] && isMatch(s+1, p+1);
		}
	}
	else
	{
		// normal character
		if(p[1] == '*')
		{
			if(isMatch(s, p+2))
				return true;

			for(const char *snext=s; ; ++snext)
			{
				if(snext[0] != p[0])
					return false;

				if(isMatch(snext+1, p+2))
					return true;
			}
		}
		else
		{
			return (s[0] == p[0]) && isMatch(s+1, p+1);
		}
	}
}


int main()
{
	string s, p;
	while(true)
	{
		cin >> s >> p;
		cout << isMatch(s.c_str(),p.c_str()) << '\n';
	}
}

Previous     Next