Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Regular Expression Matching 🧠

LeetCode Link: Regular Expression Matching

Difficulty: Hard

Problem Explanation 📝

Problem: LeetCode 10 - Regular Expression Matching

Description: 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).

Intuition: This problem can be solved using dynamic programming. We can break down the problem into smaller subproblems and use a 2D DP table to store the results of these subproblems.

Approach:

  1. Create a 2D DP table of size (s.length() + 1) x (p.length() + 1), where s.length() and p.length() are the lengths of the input string "s" and pattern "p", respectively.
  • dp[i][j] represents whether the substring s[0...i-1] matches the pattern p[0...j-1].
  1. Initialize the DP table:
  • dp[0][0] represents whether an empty string matches an empty pattern, which is true. So, dp[0][0] = true.
  • dp[i][0] represents whether an empty string matches the pattern p[0...i-1]. For all i > 0, dp[i][0] is false because a non-empty pattern cannot match an empty string.
  • For dp[0][j], we need to handle patterns with '', which means we should check if p[j-1] is '' and if there's a valid pattern before it. If yes, then dp[0][j] will have the same result as dp[0][j-2].
  1. Fill in the DP table by considering the following cases:
  • If p[j-1] is a regular character or '.', we need to check if s[i-1] matches p[j-1]. If yes, then dp[i][j] will be true if dp[i-1][j-1] is true.
  • If p[j-1] is '', we have two sub-cases: a) If the character before '' in the pattern (p[j-2]) matches the current character in the string (s[i-1]) or it is '.', then we have two options:
  • Ignore the '*' and the preceding character in the pattern: dp[i][j] will be true if dp[i][j-2] is true.
  • Consider the '*' and the preceding character in the pattern: dp[i][j] will be true if dp[i-1][j] is true and s[i-1] matches the preceding character in the pattern (p[j-2]).
  1. The final answer will be stored in dp[s.length()][p.length()], representing whether the entire string "s" matches the entire pattern "p".

Time Complexity: The time complexity of the DP solution is O(s.length() * p.length()), where s.length() and p.length() are the lengths of the input string "s" and pattern "p", respectively. We fill in the entire DP table of size (s.length() + 1) x (p.length() + 1).

💾 Space Complexity: The space complexity of the DP solution is O(s.length() * p.length()), where s.length() and p.length() are the lengths of the input string "s" and pattern "p", respectively. We use a 2D DP table to store the results of subproblems.

Dynamic Programming:

  • Subproblem: The subproblem is whether a substring s[0...i-1] matches a pattern p[0...j-1].
  • Recurrence Relation: The result for dp[i][j] depends on whether s[i-1] matches p[j-1] and the results of previous subproblems (dp[i-1][j-1], dp[i-1][j], dp[i][j-2]).
  • Base Case: The base cases are dp[0][0], dp[i][0] (for all i > 0), and dp[0][j] (for patterns with '*').

Solutions 💡

Cpp 💻

class Solution {
  public:
    bool isMatch(string s, string p) {
        int m = s.length();
        int n = p.length();
        // Create a 2D DP table and initialize base cases
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        // Base case: an empty pattern matches an empty string
        dp[0][0] = true;

        // Initialize the first row for pattern p
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                // If the current character in pattern is '*', it can match zero or more of the preceding element
                // So, we check if it matches two characters back in the pattern (j - 2) for an empty string
                dp[0][j] = dp[0][j - 2];
            }
        }

        // Fill in the DP table row by row
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    // If the current pattern character matches the current string character or it's a '.',
                    // we take the value from the diagonal (dp[i - 1][j - 1]) as the result for the current cell
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p[j - 1] == '*') {
                    // If the current pattern character is '*', it can match zero or more of the preceding element
                    // So, we check if it matches two characters back in the pattern (j - 2) for an empty string
                    // or if the current string character matches the preceding pattern character
                    // (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))
                    dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                }
            }
        }

        return dp[m][n]; // The last cell (dp[m][n]) contains the result for the entire matching process
    }
};

/*
// Beats 100% Runtime and O(n) space complexity

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length();
        int n = p.length();

        // Create a 1D DP array to store the matching results
        vector<bool> dp(n + 1, false);

        // Base case: an empty pattern matches an empty string
        dp[0] = true;

        // Initialize the DP array for the first row (when i = 0)
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                // If the current character is '*', it can match zero or more of the preceding element
                // So, we check if it matches two characters back in the pattern (j - 2)
                dp[j] = dp[j - 2];
            }
        }

        // Fill in the DP array row by row
        for (int i = 1; i <= m; i++) {
            bool prevDiagonal = dp[0]; // Store the value of the diagonal element (dp[i - 1][j - 1]) before updating it
            dp[0] = false; // Update the base case for each row, as a non-empty pattern cannot match an empty string

            // Iterate through the pattern characters
            for (int j = 1; j <= n; j++) {
                bool temp = dp[j]; // Store the current value of dp[i][j] before updating it

                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    // If the current pattern character matches the current string character or it's a '.',
                    // we take the value from the diagonal (dp[i - 1][j - 1]) as the result for the current cell
                    dp[j] = prevDiagonal;
                } else if (p[j - 1] == '*') {
                    // If the current pattern character is '*', it can match zero or more of the preceding element
                    // So, we check if it matches two characters back in the pattern (j - 2) or if the current string
                    // character matches the preceding pattern character (dp[j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'))
                    dp[j] = dp[j - 2] || (dp[j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                } else {
                    // If the characters don't match and there's no wildcard, update the cell to false
                    dp[j] = false;
                }

                prevDiagonal = temp; // Update the diagonal element for the next iteration
            }
        }

        return dp[n]; // The last cell (dp[m][n]) contains the result for the entire matching process
    }
};
*/

Python 🐍

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        # Create a 2D table dp to store whether s[:i] matches p[:j].
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # Base case: empty string matches empty pattern.
        dp[0][0] = True

        # Fill the first row of dp based on '*' in the pattern.
        for j in range(2, n + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 2]

        # Fill the dp table based on characters in s and p.
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == ".":
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == "*":
                    dp[i][j] = dp[i][j - 2] or (
                        dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == ".")
                    )

        return dp[m][n]