Leetcode 10: Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

'.' 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

Code 1:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        
        if len(p)>=2 and p[1] == "*":
            return  s != "" and (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p) or self.isMatch(s, p[2:])         
        else:
            return s != "" and (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])

Reference: http://xiaohuiliucuriosity.blogspot.com/2014/12/regular-expression-matching.html

Idea:

This is a recursive method.  You start to “consume” `p` and `s` until `p` can be consumed to empty.  If at this moment `s` happens to be consumed to empty also, your match is successful.

Everytime you look at the first and the second character in `p`. There are two situations:

If you find the second character in `p` is “*”. This means, on the left of “*” in p, there is another character, `x`, for example:

p:   x*......

s:   ...............

Then, there are three conditions:

a) `x` is not `.` and the first position of `s` is not the same as `x`. Then you must skip `x*` in p to  continue to match `s`.  So you rely on `isMatch(s, p[2:])`.

b) `x` is not `.` and the first position of `s` is the same as `x`. Then whether `p` matches `s` will depend on ‘isMatch(s[1:], p)’ or `isMatch(s, p[2:])`. You can imagine that the following match will continue to try if the `s`’s following substring  starts with `x*`. 

c) `x` is `.`. Then whether `p` matches `s` will also depend on `isMatch(s[1:], p)`

If you find the second character in `p` is not “*”, then a successful match will only happen if the first character of `p` and `s` are the same and `isMatch(s[1:], p[1:])`, i.e., the rest of `p` and `s` match.

The most bottom case of `isMatch` will only return True when `p` is empty and `s` is empty also. This means `s` has all been matched by `p` without anything left unmatched. Notice that line 12 and line 14 will return False immediately if `s` is empty. This means there are something left in `p` but you have consumed all `s`.

However, this method can’t pass Leetcode OJ written in Python. The time complexity is large because you are essentially exhausting all possible situations. Naturally, you can convert such algorithm into DP.

Code 2:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        table = [[False] * (len(s)+1) for _ in xrange(len(p)+1)]
        table[0][0] = True
        for i in xrange(2, len(p)+1):
            table[i][0] = p[i-1] == '*' and table[i-2][0]
            
        for i in xrange(1, len(p)+1):
            for j in xrange(1, len(s)+1):
                if p[i-1] == '*':
                    table[i][j] = (p[i-2] == '.' or p[i-2] == s[j-1]) and table[i][j-1] or table[i-2][j]
                else:
                    table[i][j] = (p[i-1] == '.' or p[i-1] == s[j-1]) and table[i-1][j-1]


        return table[-1][-1]

Reference: https://leetcode.com/discuss/55253/my-dp-approach-in-python-with-comments-and-unittest

Idea:

It is a DP algorithm. table[i][j] records whether p[0:i] matches s[0:j]. table[0][0] is True because “” matches “”. table[i][0] is the result of a pattern matching “”. It will only be true if `p` only contains `x*` pattern. table[0][j] will always be False because an empty pattern will not be able to match any string. 

Then, we start to update table[i][j], column first.

If p[i-1] == “*”, table[i][j] will be true if:

1. p[i-1] equals to s[j-1] and p[0:i] matches s[0:j-1] (str1 + “x*” matches str2 => str1 + “x*” matches str2 + “x”),
2. p[0:i-1] matches s[0:j] (str1 matches str2 => str1+”x*” matches str2) 

if p[i-1] is not “*”, table[i][j] will be true if p[0:i-1] matches s[0:j-1] (str1 matches str2 => str1+”x” matches str2+”x”)

This algorithm uses O(|p||s|) space to get fast running time. It is accepted by Leetcode finally.