Regular Expression Matching

Problem

Implement regex matching with support for “.” (any single char) and “*” (zero or more of the preceding element).

Example

Input:  s = "aab", p = "c*a*b"
Output: true

Solution

2D DP. dp[i][j] = whether s[:i] matches p[:j]. Special handling for * which can match 0 or more chars.

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for j in range(1, n + 1):
        if p[j-1] == '*': dp[0][j] = dp[0][j-2]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2]
                if p[j-2] == s[i-1] or p[j-2] == '.':
                    dp[i][j] = dp[i][j] or dp[i-1][j]
            elif p[j-1] == s[i-1] or p[j-1] == '.':
                dp[i][j] = dp[i-1][j-1]
    return dp[m][n]

function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(false));
    dp[0][0] = true;
    for (let j = 1; j <= n; j++) {
        if (p[j-1] === '*') dp[0][j] = dp[0][j-2];
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j-1] === '*') {
                dp[i][j] = dp[i][j-2];
                if (p[j-2] === s[i-1] || p[j-2] === '.') dp[i][j] = dp[i][j] || dp[i-1][j];
            } else if (p[j-1] === s[i-1] || p[j-1] === '.') {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[m][n];
}

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) if (p[j-1] == '*') dp[0][j] = dp[0][j-2];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2];
                if (p[j-2] == s[i-1] || p[j-2] == '.') dp[i][j] = dp[i][j] || dp[i-1][j];
            } else if (p[j-1] == s[i-1] || p[j-1] == '.') {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[m][n];
}

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

Complexity

Time: O(m * n)
Space: O(m * n)

Explanation

For * we have two choices: ignore the pattern pair (zero matches) or use it to match one more char of s. The base case handles patterns like “a*b*” matching empty string.

#Dynamic Programming #Recursion #String

Comments

Join the discussion. Got a question, found an issue, or want to share your experience?

Problem

Example

Solution

Complexity

Explanation

Leave a Comment Cancel