#include "stdafx.h"
#include "assert.h"
bool isMatch(const char *s, const char *p) {
if (!*p) return !*s;
if (*(p+1) != '*' && *(p+1) != '+')
return (*s == *p) && isMatch(s+1, p+1);
if ( *(p+1) == '+') {
if (*s != *p) return false;
++s;
}
while( *s == *p) {
if (isMatch(s, p+2)) return true;
s++;
}
return isMatch(s, p+2);
}
int _tmain(int argc, _TCHAR* argv[])
{
assert(isMatch("", ""));
assert(!isMatch("a", ""));
assert(!isMatch("aa", ""));
assert(!isMatch("aaa", ""));
assert(!isMatch("", "a"));
assert(!isMatch("", "aa"));
assert(!isMatch("", "aaa"));
assert(!isMatch("a", "aa"));
assert(!isMatch("aa", "a"));
assert(isMatch("a", "a"));
assert(isMatch("ab", "ab"));
assert(isMatch("a", "a*"));
assert(isMatch("a", "a+"));
assert(isMatch("aa", "a*"));
assert(isMatch("aa", "a+"));
assert(isMatch("aaa", "a+"));
assert(isMatch("aaa", "a+"));
assert(!isMatch("aab", "a+"));
assert(!isMatch("aab", "a+"));
assert(isMatch("aab", "a*b"));
assert(isMatch("aab", "a+b"));
assert(isMatch("aab", "a*b+"));
assert(isMatch("aab", "a+b*"));
assert(isMatch("aabbc", "a+b+c"));
assert(isMatch("aabbc", "a+b*c"));
assert(isMatch("aabbc", "aa*b*c"));
assert(isMatch("aabbc", "aa+bb+c"));
return 0;
}
Online Judge Solutions
- Google (1)
- LeetCode Solutions (32)
- LintCode Solutions (68)
- Marked (38)
- Misc. (8)
Tuesday, February 17, 2015
Regular Expression match with * and +
This one was from Facebook Seattle Onsite (asked by an Indian guy :))
Given a source string (doesn't contain '*' or '+') and a pattern string (may contain zero or more '+' or '*'). Check if the source matches the pattern.
'*' mean the letter before it can appear 0 or more times
'+' mean the letter before it can appear 1 or more times
ie:
aab matches a+b or a*b
abc doesn't match ad+bc but matches ad*bc.
Labels:
Marked
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment