# Regular Expression Matching
**Difficulty:** HARD
[External](https://leetcode.com/problems/regular-expression-matching)
Canonical: https://scaleengineer.com/dsa/problems/regular-expression-matching
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Coupang](https://scaleengineer.com/companies/coupang), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Turing](https://scaleengineer.com/companies/turing), [Citadel](https://scaleengineer.com/companies/citadel), [Confluent](https://scaleengineer.com/companies/confluent), [Hiver](https://scaleengineer.com/companies/hiver), [WinZO](https://scaleengineer.com/companies/winzo), [WorldQuant](https://scaleengineer.com/companies/worldquant), [X](https://scaleengineer.com/companies/x)
---
## Problem
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).

**Example 1:**

**Input:** s = "aa", p = "a"
**Output:** false
**Explanation:** "a" does not match the entire string "aa".

**Example 2:**

**Input:** s = "aa", p = "a*"
**Output:** true
**Explanation:** '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

**Example 3:**

**Input:** s = "ab", p = ".*"
**Output:** true
**Explanation:** ".*" 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.

# Approaches
## Brute-Force Recursion
A straightforward recursive approach that directly translates the problem definition into a recursive function. It explores all possible matching paths without memoization, leading to redundant computations for the same subproblems.
**Time:** O((S+P) * 2^(S+P/2)) · **Space:** O(S + P)
**Pros:** Simple to understand and implement directly from the problem's recursive definition.
**Cons:** Extremely inefficient due to re-computation of overlapping subproblems.; Can lead to a "Time Limit Exceeded" error on many platforms for non-trivial inputs.
### Explanation
The core idea is to define a function `isMatch(text, pattern)` that checks if the `text` matches the `pattern`. The recursion proceeds by considering the first characters of the current text and pattern.

- **Base Case:** If the pattern is empty, the text must also be empty for a match.
- **Recursive Step:**
    - We check if the first character of the text matches the first character of the pattern (or if the pattern character is '.').
    - If the second character of the pattern is `*`:
        - We have two choices:
            1. The `*` matches zero preceding elements. We skip this part of the pattern (`pattern.substring(2)`) and see if it matches the current text.
            2. The `*` matches one or more preceding elements. This is only possible if the first characters match. If they do, we move to the next character in the text (`text.substring(1)`) and try to match it against the same pattern (since `*` can match multiple characters).
        - The result is `true` if either choice leads to a match.
    - If the second character is not `*`:
        - We must have a match of the first characters. If so, we recursively call the function for the rest of the text and pattern (`text.substring(1)`, `pattern.substring(1)`).

This approach suffers from re-calculating the same subproblems multiple times, leading to exponential time complexity in the worst case.

```java
class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean firstMatch = (!s.isEmpty() &&
                              (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));

        if (p.length() >= 2 && p.charAt(1) == '*') {
            // Case 1: '*' matches zero preceding element
            // Case 2: '*' matches one or more preceding element
            return (isMatch(s, p.substring(2)) ||
                    (firstMatch && isMatch(s.substring(1), p)));
        } else {
            // No '*'
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
    }
}
```
### Algorithm
1. Define a recursive function `isMatch(s, p)`.
2. **Base Case:** If `p` is empty, return `true` if `s` is also empty, otherwise `false`.
3. Let `first_match` be `true` if `s` is not empty and its first character matches `p`'s first character (or `p`'s first character is '.').
4. If `p` has length >= 2 and its second character is `*`:
   - Return `isMatch(s, p.substring(2))` (treating `x*` as zero occurrences) OR (`first_match` AND `isMatch(s.substring(1), p)`) (treating `x*` as one or more occurrences).
5. Otherwise (no `*`):
   - Return `first_match` AND `isMatch(s.substring(1), p.substring(1))`.

## Top-Down Dynamic Programming with Memoization
This approach optimizes the brute-force recursion by using a memoization table (a cache) to store the results of subproblems that have already been solved. This avoids redundant computations and significantly improves performance.
**Time:** O(S * P) · **Space:** O(S * P)
**Pros:** Much more efficient than brute-force recursion.; Guarantees that each subproblem is solved only once.
**Cons:** Uses extra space for the memoization table and the recursion stack.
### Explanation
We use a 2D array, say `memo`, to store the results of the function calls. `memo[i][j]` will store the result of whether `s.substring(i)` matches `p.substring(j)`. The recursive function, let's call it `dp(i, j)`, now takes indices `i` and `j` for the string `s` and pattern `p` respectively. Before any computation, `dp(i, j)` first checks if `memo[i][j]` has already been computed. If so, it returns the stored value immediately. If not, it computes the result using the same logic as the brute-force recursive approach. After computing the result, it stores it in `memo[i][j]` before returning. The initial call would be `dp(0, 0)`.

```java
class Solution {
    Boolean[][] memo;

    public boolean isMatch(String s, String p) {
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return dp(0, 0, s, p);
    }

    private boolean dp(int i, int j, String s, String p) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        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 = (dp(i, j + 2, s, p) ||
                       (firstMatch && dp(i + 1, j, s, p)));
            } else {
                ans = firstMatch && dp(i + 1, j + 1, s, p);
            }
        }
        memo[i][j] = ans;
        return ans;
    }
}
```
### Algorithm
1. Create a memoization table `memo[s.length() + 1][p.length() + 1]` to store results of subproblems. Initialize with a value indicating "not computed" (e.g., null).
2. Define a recursive helper function `dp(i, j, s, p, memo)`.
3. Inside `dp`, check if `memo[i][j]` is already computed. If yes, return the stored value.
4. **Base Case:** If `j` reaches the end of `p`, the result is `true` if `i` has also reached the end of `s`.
5. Let `first_match` be `true` if `i < s.length()` and `s[i]` matches `p[j]`.
6. If `j+1 < p.length()` and `p[j+1]` is `*`:
   - Calculate the result as `dp(i, j + 2, ...)` OR (`first_match` AND `dp(i + 1, j, ...)`).
7. Otherwise (no `*`):
   - Calculate the result as `first_match` AND `dp(i + 1, j + 1, ...)`.
8. Store the calculated result in `memo[i][j]` and return it.

## Bottom-Up Dynamic Programming
This is an iterative approach to dynamic programming that builds the solution from the smallest subproblems up to the final solution. It uses a 2D table to store the results, similar to memoization, but fills it iteratively, eliminating recursion overhead.
**Time:** O(S * P) · **Space:** O(S * P)
**Pros:** Most efficient and standard solution.; Avoids recursion overhead, which can make it slightly faster in practice than the top-down approach.
**Cons:** Can be less intuitive to formulate than the recursive solution.; Still requires O(S*P) space.
### Explanation
We create a 2D boolean table `dp` of size `(s.length() + 1) x (p.length() + 1)`. `dp[i][j]` will be `true` if the first `i` characters of `s` (i.e., `s.substring(0, i)`) match the first `j` characters of `p` (i.e., `p.substring(0, j)`).

- **Initialization:**
    - `dp[0][0] = true`: An empty string matches an empty pattern.
    - For the first row (`i=0`), `dp[0][j]` can be true only if the pattern `p.substring(0, j)` can match an empty string. This happens when the pattern is of the form `a*b*c*...`. So, `dp[0][j] = dp[0][j-2]` if `p.charAt(j-1) == '*'`. 

- **Iteration:**
    - We fill the table row by row, column by column, from `i=1` to `s.length()` and `j=1` to `p.length()`.
    - For each cell `dp[i][j]`:
        - If `p.charAt(j-1)` is a normal character or `.`: `dp[i][j]` is true if `dp[i-1][j-1]` is true and the current characters `s.charAt(i-1)` and `p.charAt(j-1)` match.
        - If `p.charAt(j-1)` is `*`: This `*` refers to `p.charAt(j-2)`. We have two possibilities: 
          1. The `p.charAt(j-2)*` part matches zero characters. The result is determined by `dp[i][j-2]`.
          2. The `p.charAt(j-2)*` part matches one or more characters. This requires `s.charAt(i-1)` to match `p.charAt(j-2)`. If it does, the result depends on `dp[i-1][j]`.
          So, `dp[i][j] = dp[i][j-2] || (first_match && dp[i-1][j])`.

The final answer is `dp[s.length()][p.length()]`.

```java
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        // Deals with patterns like a* or a*b* or a*b*c*
        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 sChar = s.charAt(i - 1);
                char pChar = p.charAt(j - 1);

                if (pChar == '.' || pChar == sChar) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChar == '*') {
                    // Case 1: '*' matches zero preceding element
                    dp[i][j] = dp[i][j - 2];
                    
                    // Case 2: '*' matches one or more preceding element
                    char prevPChar = p.charAt(j - 2);
                    if (prevPChar == '.' || prevPChar == sChar) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}
```
### Algorithm
1. Create a 2D boolean DP table `dp` of size `(s.length() + 1) x (p.length() + 1)`.
2. Initialize `dp[0][0] = true`.
3. Initialize the first row: `dp[0][j]` is `true` if `p[j-1]` is `*` and `dp[0][j-2]` is `true`. This handles patterns like `a*`, `a*b*`, etc., matching an empty string.
4. Iterate `i` from 1 to `s.length()` and `j` from 1 to `p.length()`.
5. If `p[j-1]` is `.` or `p[j-1] == s[i-1]`:
   - `dp[i][j] = dp[i-1][j-1]`.
6. If `p[j-1]` is `*`:
   - `dp[i][j] = dp[i][j-2]` (zero occurrences of `p[j-2]`)
   - If `p[j-2]` is `.` or `p[j-2] == s[i-1]`:
     - `dp[i][j] = dp[i][j] || dp[i-1][j]` (one or more occurrences).
7. Otherwise (mismatch):
   - `dp[i][j] = false`.
8. Return `dp[s.length()][p.length()]`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length, n = p.Length;
        bool[, ] f = new bool[m + 1, n + 1];
        f[0, 0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i, j] = f[i, j - 2];
                    if (i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {
                        f[i, j] |= f[i - 1, j];
                    }
                } else if (i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {
                    f[i, j] = f[i - 1, j - 1];
                }
            }
        }
        return f[m, n];
    }
}
```

### Java

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

```

### JavaScript

```javascript
/** * @param {string} s * @param {string} p * @return {boolean} */ var isMatch =
  function (s, p) {
    const m = s.length;
    const n = p.length;
    const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    f[0][0] = true;
    for (let i = 0; i <= m; ++i) {
      for (let j = 1; j <= n; ++j) {
        if (p[j - 1] === " * ") {
          f[i][j] = f[i][j - 2];
          if (i && (p[j - 2] === " . " || p[j - 2] === s[i - 1])) {
            f[i][j] |= f[i - 1][j];
          }
        } else if (i && (p[j - 1] === " . " || p[j - 1] === s[i - 1])) {
          f[i][j] = f[i - 1][j - 1];
        }
      }
    }
    return f[m][n];
  };

```

### CPP

```cpp
class Solution {
public:
  bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    bool f[m + 1][n + 1];
    memset(f, false, sizeof f);
    f[0][0] = true;
    for (int i = 0; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (p[j - 1] == '*') {
          f[i][j] = f[i][j - 2];
          if (i && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {
            f[i][j] |= f[i - 1][j];
          }
        } else if (i && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {
          f[i][j] = f[i - 1][j - 1];
        }
      }
    }
    return f[m][n];
  }
};

```

### Python

```python
class Solution:
    def isMatch(self, s: str, p: str) -> bool: m, n = len(s), len(p) f = [[False] * (n + 1) for _ in range(m + 1)] f[0][0] = True for i in range(m + 1): for j in range(1, n + 1): if p[j - 1] == "*": f[i][j] = f[i][j - 2] if i > 0 and (p[j - 2] == "." or s[i - 1] == p[j - 2]): f[i][j] |= f[i - 1][j] elif i > 0 and (p[j - 1] == "." or s[i - 1] == p[j - 1]): f[i][j] = f[i - 1][j - 1] return f[m][n]

```