10.Regular Expression Matching

Tags: [recursion], [regex], [dp]

Com: {fb}

Link: https://leetcode.com/problems/regular-expression-matching/#/description

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: Recursion, DP (top to bottom)

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if not p:
            return not s

        memo = [[None for _ in xrange(len(p))] for _ in xrange(len(s))]
        return self.is_match_helper(s, 0, p, 0, memo)

    def is_match_helper(self, s, s_index, p, p_index, memo):
        # base case
        if s_index >= len(s) and p_index >= len(p):
            return True

        if s_index >= len(s):
            if (len(p) - p_index) % 2 != 0:
                return False
            else:
                for i in xrange(p_index, len(p) - 1, 2):
                    if not (p[i] != '*' and p[i + 1] == '*'):
                        return False
                return True

        if p_index >= len(p):
            if len(p) < 2 or p[-1] != '*':
                return False
            else:
                return all([s[i] == p[-2] for i in xrange(s_index, len(s))])

        if memo[s_index][p_index] is not None:
            return memo[s_index][p_index]

        if p_index + 1 >= len(p) or p[p_index + 1] != '*':
            # the next char of p is not '*'
            result =  self.is_single_match(s, s_index, p, p_index) and\
                      self.is_match_helper(s, s_index + 1, p, p_index + 1, memo)
            memo[s_index][p_index] = result
            return result
        else:
            # the next char of p is '*'
            # current sub p pattern maches nothing
            if self.is_match_helper(s, s_index, p, p_index + 2, memo):
                memo[s_index][p_index] = True
                return True

            # current sub p pattern maches the part of s
            # try all possible length of sub s to match the sub p pattern
            original_s_index = s_index
            while self.is_single_match(s, s_index, p, p_index):
                if self.is_match_helper(s, s_index + 1, p, p_index, memo):
                    return True
                s_index += 1

            memo[original_s_index][p_index] = False
            return False

    def is_single_match(self, s, s_index, p, p_index):
        if s_index >= len(s) or p_index >= len(p):
            return False

        return p[p_index] == '.' or s[s_index] == p[p_index]

Revelation:

• The more understanding way to implement regular expression is recursion + dp(top to bottom).

Note:

• Time complexity = O(len(s) * len(p)), because we just to fill the memo, and each cell of the memo (memo[s_index][p_index]) is only calculated by once.

Follow-up:

• How to implement the above algorithm by dp (bottom to top)?

• How to implement the regular expression also with '+' and '?'