Regular Expression Matching

Problem: Regular Expression Matching

With string "Sc" and parameter "Pp", where S is a sub-string and P is a sub-parameter, it's clear that whether these two match is decided based on isMatch(S, P) and isMatch(Sc, P). Thus, we can use dynamic programming to solve this problem. By testing, we can find all judging criteria we need.

Code in Python:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m, n = len(s), len(p)
        dp = [[True] + [False] * m]
        for i in xrange(n):
            dp.append([False] * (m+1))

        for i in xrange(1, n+1):
            x = p[i-1]
            if x == '*' and i > 1:  // Judge 1
                dp[i][0] = dp[i-2][0]
            for j in xrange(1, m+1):
                if x == '*':    // Judge 2 or 3 or 4 or 5
                    dp[i][j] = dp[i-2][j] or dp[i-1][j] or (dp[i-1][j-1] and p[i-2] == s[j-1]) or (dp[i][j-1] and p[i-2] == '.')
                elif x == s[j-1] or x == '.':   // Judge 6
                    dp[i][j] = dp[i-1][j-1]

        return dp[n][m]

To understand these 6 statements better, working through the given example is strongly recommended,

Code in Java:

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.equals(p)) return true;
        if (p.length() == 0) return false;
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        dp[0][1] = false;
        for (int i = 2; i <= n; i++) {
            if (dp[0][i-2] && p.charAt(i-1) == '*') {
                dp[0][i] = true;
            }
        }
        for (int i = 1; i <= m; i++) {
            dp[i][0] = false;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if ((s.charAt(i-1) == p.charAt(j-1) && dp[i-1][j-1]) ||
                    (p.charAt(j-1) == '*' && dp[i][j-1]) ||
                    (p.charAt(j-1) == '*' && p.charAt(j-2) == s.charAt(i-1) && dp[i-1][j]) ||
                    (p.charAt(j-1) == '.' && dp[i-1][j-1]) ||
                    (p.charAt(j-1) == '*' && p.charAt(j-2) == '.' && dp[i-1][j]) ||
                    (p.charAt(j-1) == '*' && dp[i][j-2])) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}