Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Hard

Regular Expression Matching

Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` and `'*'` where: - `'.'` Matches any single character. - `'*'` Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Examples

Input:s = "aa", p = "a"
Output:false
"a" does not match the entire string "aa".
Input:s = "aa", p = "a*"
Output:true
'*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Input:s = "ab", p = ".*"
Output:true
".*" means "zero or more (*) of any character (.)".

Constraints

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Dynamic Programming (Top-Down with Memoization)

Approach

We can use a recursive function `dfs(i, j)` to determine if `s[i:]` and `p[j:]` match. If `p[j+1]` is a `*`, we have two choices: 1. Don't use the `*` (which means deleting the character and the `*`): `dfs(i, j+2)` 2. Use the `*` (if `s[i]` matches `p[j]`): `dfs(i+1, j)` If `p[j+1]` is not `*`, we just check if `s[i]` matches `p[j]`, and if so, move to the next characters: `dfs(i+1, j+1)`. We cache the results of `(i, j)` in a memoization map to avoid redundant calculations.

Complexity Analysis

Time Complexity
O(S * P)
Space Complexity
O(S * P)

S is the length of string s and P is the length of string p. The number of unique states is S * P, and the work done at each state is O(1). Therefore, time and space complexity are both O(S * P).

Solution.java
class Solution {    public boolean isMatch(String s, String p) {        // memo[i][j]: 0=uncomputed, 1=true, -1=false        int[][] memo = new int[s.length() + 1][p.length() + 1];        return dfs(0, 0, s, p, memo);    }        private boolean dfs(int i, int j, String s, String p, int[][] memo) {        if (memo[i][j] != 0) {            return memo[i][j] == 1;        }                boolean ans;        if (j == p.length()) {            ans = i == s.length();        } else {            boolean firstMatch = (i < s.length() &&                                    (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'));                                               if (j + 1 < p.length() && p.charAt(j + 1) == '*') {                ans = (dfs(i, j + 2, s, p, memo) ||                        (firstMatch && dfs(i + 1, j, s, p, memo)));            } else {                ans = firstMatch && dfs(i + 1, j + 1, s, p, memo);            }        }                memo[i][j] = ans ? 1 : -1;        return ans;    }}