Last updated on March 9th, 2025 at 09:13 pm

Here, we see a Regular Expression Matching LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking, Dynamic Programming, String

Companies

Airbnb, Facebook, Google, Twitter, Uber

Level of Question

Hard

Regular Expression Matching LeetCode Solution

1. Problem Statement

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 (.)".
 

2. Coding Pattern Used in Solution

The provided code implements the Dynamic Programming (DP) pattern. This pattern is used to solve problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results for future use to avoid redundant computations.

The specific problem being solved here is Regular Expression Matching, where the goal is to determine if a given string s matches a pattern p that may include special characters like . (matches any single character) and * (matches zero or more of the preceding element).

3. Code Implementation in Different Languages

3.1 Regular Expression Matching C++

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<bool> pre(n + 1, false), cur(n + 1, false);
        cur[0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    cur[j] = cur[j - 2] || (i && pre[j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                } else {
                    cur[j] = i && pre[j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
            fill(pre.begin(), pre.end(), false);
			swap(pre, cur);
        }
        return pre[n];
    }
};

3.2 Regular Expression Matching Java

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

3.3 Regular Expression Matching JavaScript

var isMatch = function(s, p) {
     var lenS = s.length;
  var lenP = p.length;
  var map = {};

  return check(0, 0);

  function check(idxS, idxP) {
    if (map[idxS + ':' + idxP] !== undefined) return map[idxS + ':' + idxP];
    if (idxS > lenS) return false;
    if (idxS === lenS && idxP === lenP) return true;

    if (p[idxP] === '.' || p[idxP] === s[idxS]) {
      map[idxS + ':' + idxP] = p[idxP + 1] === '*' ?
        check(idxS + 1, idxP) || check(idxS, idxP + 2) :
        check(idxS + 1, idxP + 1);
    } else {
      map[idxS + ':' + idxP] = p[idxP + 1] === '*' ?
        check(idxS, idxP + 2) : false;
    }
    return map[idxS + ':' + idxP];
    }
};

3.4 Regular Expression Matching Python

class Solution(object):
    def isMatch(self, s, p):
        dp = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]
        dp[0][0] = True
        for i in range(1, len(p)):
            dp[i + 1][0] = dp[i - 1][0] and p[i] == '*'
        for i in range(len(p)):
            for j in range(len(s)):
                if p[i] == '*':
                    dp[i + 1][j + 1] = dp[i - 1][j + 1] or dp[i][j + 1]
                    if p[i - 1] == s[j] or p[i - 1] == '.':
                        dp[i + 1][j + 1] |= dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j] and (p[i] == s[j] or p[i] == '.')
        return dp[-1][-1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(m * n)	O(n)
Java	O(m * n)	O(m * n)
JavaScript	O(m * n)	O(m * n)
Python	O(m * n)	O(m * n)