How to Solve Regular Expression Matching

Written By
Adam Bhula

Regular Expression Matching Introduction

The Regular Expression Matching problem asks us to validate whether a pattern p matches an input string. The problem requires us to create a dynamic programming table, moving through each cell, updating its value based on a set of rules correlating to the rules set up in the original question.

Regular Expression Matching Problem

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

Example Inputs and Outputs

Example 1

Input: s = "aa", p = "a"
Output: false

Example 2

Input: s = "aa", p = "a*"
Output: True

Example 3

Input: s = "ab", p = ".*"
Output: true

Regular Expression Matching Solutions

To solve this problem, we use dynamic programming to determine whether a given string matches a pattern. We create a dynamic programming table of size (m + 1) x (n + 1), where m is the length of the string and n is the length of the pattern. Each cell in the table represents whether a substring of the string and a substring of the pattern match.

We start by initializing the table with False values. Then, we set the first cell to True because an empty string matches an empty pattern. Moving through each cell in the table, we update its value based on specific rules.

If the pattern character is a letter or '.', we compare the current string character to the current pattern character. If they match, the current cell's value depends on the previous matching state. Otherwise, the current cell remains False.

If the pattern character is ''", we have two possibilities. The ''" can match zero occurrences of the preceding element, in which case we consider the pattern without the preceding element. Alternatively, the '*' can match one or more occurrences of the preceding element. We check if the current string character matches the preceding pattern character, and if they do, the current cell's value depends on a previous cell.

Finally, we obtain the result from the last cell in the table, indicating whether the entire string matches the entire pattern.

def isMatch(s, p):
    m, n = len(s), len(p)

    # Create a 2D boolean array to store the matching results
    dp = [[False] * (n + 1) for _ in range(m + 1)]

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

    # Update the first row to handle patterns with '*'
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 2]

    # Fill in the rest of the dp array
    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] == '.':
                # Characters match or pattern has '.'
                dp[i][j] = dp[i - 1][j - 1]
            elif p[j - 1] == '*':
                # Pattern has '*', check the preceding character
                dp[i][j] = dp[i][j - 2]
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    dp[i][j] |= dp[i - 1][j]

    return dp[m][n]

# Driver code
s = "cbaab"
p = "c.a*b"
result = isMatch(s, p)
print(f"String '{s}' matches pattern '{p}': {result}")

#expected result is True

Time/Space Complexity Analysis

  • Time Complexity: O(m * n), where m is the length of the string s and n is the length of the pattern p. This is because we need to iterate through each character in the string and pattern to fill the dynamic programming table.
  • Space Complexity: O(m * n), as we need to create a dynamic programming table to store the intermediate results.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.