Back to DSA

Regular Expression Matching

hard
Acceptance: 36%
Dynamic Programming

Implement a pattern matcher that supports two special characters: '.' which matches any single character, and '*' which matches zero or more repetitions of the character immediately before it. The match must account for the entire input string, not just a substring.

Examples

Example 1:
Input:s = "abbc", p = "a.*c"
Output:true
Explanation: '.' followed by '*' matches any number of any character, covering 'bb'. Then 'c' matches 'c'.
Example 2:
Input:s = "hello", p = "he*lo"
Output:false
Explanation: 'e*' can match zero or more 'e's, giving 'hlo' or 'helo' or 'heelo' etc., but none equals 'hello'.

Hints

Related Problems

House RobbermediumClimbing StairseasyLongest Increasing SubsequencemediumWord BreakmediumEdit Distancehard
00:00
class Solution {
    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++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}
Time complexityO(m * n)
Space complexityO(m * n)