Tech Blogs LLD SDE Playbook DSA

Regular Expression Matching

Hard Top 250
Associated Patterns
2D Dynamic Programming
Interviewed At (Company Tags)
GoogleAmazonMicrosoftMetaApple
External Reference View on LeetCode

Problem Description

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*'.

  • '.' Matches any single character.
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Examples

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.

2D DP: Match and Wildcard Branches

Let dp[i][j] be true if s[0..i-1] matches pattern p[0..j-1]. We look at p[j - 1] and the potential next character p[j]:

  • Case 1: p[j - 1] is not *:
    • For a match, we must have s[i - 1] == p[j - 1] or p[j - 1] == '.'.
    • If it matches: dp[i][j] = dp[i - 1][j - 1].
  • Case 2: p[j - 1] is *:
    • Let the character before * be prev = p[j - 2].
    • Option A (Zero Occurrences): we can choose to treat the * as matching zero occurrences of prev. The pattern prev* is eliminated, meaning we transition from dp[i][j - 2].
    • Option B (One/More Occurrences): if s[i - 1] matches prev (i.e. s[i - 1] == prev or prev == '.'), we can consume s[i - 1] and keep the * pattern active: transition from dp[i - 1][j].
    • Thus: dp[i][j] = dp[i][j - 2] || (matches && dp[i - 1][j]).

Base cases:

  • dp[0][0] = true (empty string matches empty pattern).
  • dp[0][j]: an empty string s can match a pattern like a*b*c* where every character is followed by *. Specifically, dp[0][j] = dp[0][j - 2] if p[j - 1] == '*'.

Solution: 2D DP Matrix

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

        // base case: empty string matches patterns like a*b*c*
        for (int j = 2; j <= m; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char pChar = p.charAt(j - 1);

                if (pChar != '*') {
                    // case 1: normal character or '.'
                    if (pChar == '.' || pChar == s.charAt(i - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    // case 2: '*' wildcard
                    // option A: match 0 times (delete preceding char)
                    dp[i][j] = dp[i][j - 2];

                    // option B: match 1 or more times
                    char prevChar = p.charAt(j - 2);
                    if (prevChar == '.' || prevChar == s.charAt(i - 1)) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[n][m];
    }
}
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True

        # base case: empty string matching zero-occurrences pattern
        for j in range(2, m + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                p_char = p[j - 1]
                
                if p_char != '*':
                    if p_char == '.' or p_char == s[i - 1]:
                        dp[i][j] = dp[i - 1][j - 1]
                else:
                    # option A: match 0 times
                    dp[i][j] = dp[i][j - 2]
                    
                    # option B: match 1 or more times
                    prev_char = p[j - 2]
                    if prev_char == '.' or prev_char == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]

        return dp[n][m]
#include <vector>
#include <string>

class Solution {
public:
    bool isMatch(std::string s, std::string p) {
        int n = s.length(), m = p.length();
        std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));
        dp[0][0] = true;

        for (int j = 2; j <= m; j++) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char pChar = p[j - 1];

                if (pChar != '*') {
                    if (pChar == '.' || pChar == s[i - 1]) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i][j - 2];
                    char prevChar = p[j - 2];
                    if (prevChar == '.' || prevChar == s[i - 1]) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }

        return dp[n][m];
    }
};

Complexity Analysis:

  • Time Complexity: O(N * M) where N is the length of string s and M is the length of pattern p.
  • Space Complexity: O(N * M) to store the 2D DP matrix.

← All Problems