Online Judge Solutions

Saturday, November 22, 2014

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.
'.' 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 1, Recursion:

 bool isMatch(const char *s, const char *p) {
        if (!*p) return !*s;
       
        if (*(p+1) != '*') { return (*p == *s ||(*s && *p == '.')) && isMatch(s+1, p+1);}
       
        while(*s == *p || (*p == '.' && *s)) {
            if (isMatch(s, p+2)) return true;
            s++;
        }
        return isMatch(s, p+2);
    }

Solution 2. DP

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
       if (!*p) return !*s;
       int m = strlen(p);
       int n = strlen(s);
      
       vector<vector<bool>> match(m+1, vector<bool>(n+1, false));
      
       match[0][0] = 1;
       match[1][1] = s[0] == p[0] || p[0] == '.';
      
       // When s is empty, but p = '.*', p matches s
       for(int i = 2; i <=m; i++)
           match[i][0] = p[i-1] == '*'? match[i-2][0] : false;
       // starting from second char in p
       for(int i = 2; i <= m; i++)
           for(int j = 1; j <= n; j++)
              if (p[i-1]== '*')
                match[i][j] = isSame(s[j-1], p[i-2])? match[i-2][j] || match[i-2][j-1] || match[i-1][j-1] || match[i][j-1] : match[i-2][j];
             else 
                match[i][j] = isSame(s[j-1], p[i-1]) && match[i-1][j-1];
          
       
        return match[m][n];
    }
   
    bool isSame(char a, char b){
        return (a == b || b=='.');
    }
};

No comments:

Post a Comment