Leetcode 10. Regular Expression Matching

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

This is actually a fraction of regular expression, which is supported by Python re module.

The slick solution is to take advantage of that:
import re
...
return re.match('^' + p + '$', s) != None
This is the one line solution. Run time is 120 ms.

Of course, we can attack the problem directly. There are many solutions, and the main method is dynamic programming while the ways to use DP are rolling window, iteration or recursion. Here the rolling window method is presented because its space is O(n) while others are O(m + n).

Solution:

# T:O(m*n) S:O(n)
class Solution:
    # @return a boolean
    def isMatch(self, s, p):
        k = 3
        result = [[False for j in xrange(len(p) + 1)] for i in xrange(k)]
        
        result[0][0] = True
        for i in xrange(2, len(p) + 1):
            if p[i-1] == '*':
                result[0][i] = result[0][i-2]
        
        for i in xrange(1,len(s) + 1):
            if i > 1:
                result[0][0] = False
            for j in xrange(1, len(p) + 1):
                if p[j-1] != '*':
                    result[i % k][j] = result[(i-1) % k][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
                else:
                    result[i % k][j] = result[i % k][j-2] or (result[(i-1) % k][j] and (s[i-1] == p[j-2] or p[j-2]=='.'))
                    
        return result[len(s) % k][len(p)]

Run Time: 96 ms