Online Judge Solutions

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.


#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;
}

No comments:

Post a Comment