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)

Thoughts

喜刷刷 leetcode 2-pointer方法

Solution

class Solution:
    """
    @param s: A string 
    @param p: A string includes "." and "*"
    @return: A boolean
    """
    def isMatch(self, s, p):
        # write your code here
        lenS = len(s)
        lenP = len(p)

        dp = [[False for j in range(lenP+1)] for i in range(lenS+1)]
        dp[0][0] = True

        for i in range(lenS + 1):
            for j in range(1, lenP + 1):
                if p[j-1] != "." and p[j-1] != "*":
                    if dp[i-1][j-1] and s[i-1] == p[j-1]:
                        dp[i][j] = True
                elif p[j-1] == ".":
                    if dp[i-1][j-1]:
                        dp[i][j] = True
                elif j > 1:
                    if dp[i][j-2]:
                        dp[i][j] = True
                    if dp[i][j-1]:
                        dp[i][j] = True
                    if dp[i-1][j] and (p[j-2] == "." or s[i-1] == p[j-2]):
                        dp[i][j] = True

        return dp[lenS][lenP]