Regular Expression Matching

Question

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

Tags

• String
• Dynamic Programming
• Backtracking

Thought

Reference: https://www.youtube.com/watch?v=l3hda49XcDE

Define the dynamic programming table to store the data. The height of the table is len(string) + 1 and the width of the table is len(pattern) + 1.

Code

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