10. Regular Expression Matching - Explanation

Description

You are given an input string s consisting of lowercase english letters, and a pattern p consisting of lowercase english letters, as well as '.', and '*' characters.

Return true if the pattern matches the entire input string, otherwise return false.

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

Example 1:

Input: s = "aa", p = ".b"

Output: false

Explanation: Regardless of which character we choose for the '.' in the pattern, we cannot match the second character in the input string.

Example 2:

Input: s = "nnn", p = "n*"

Output: true

Explanation: '*' means zero or more of the preceding element, 'n'. We choose 'n' to repeat three times.

Example 3:

Input: s = "xyz", p = ".*z"

Output: true

Explanation: The pattern ".*" means zero or more of any character, so we choose ".." to match "xy" and "z" to match "z".

Constraints:

1 <= s.length <= 20
1 <= p.length <= 20
Each appearance of '*', will be preceded by a valid character or '.'.

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the length of the string s and n is the length of the string p.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, where we explore different combinations to match the strings when encountering *. Multiple decisions are made at each step to find a valid matching path. Can you determine the possible decisions at each recursion step?

Hint 2

We recursively iterate through the strings using indices i and j for s and p, respectively. If the characters match or p[j] is '.', we increment both i and j to process the remaining strings. When the next character of string p is '*', we have two choices: skip it (treating it as zero occurrences) or match one or more characters (if s[i] matches p[j]), incrementing i accordingly.

Hint 3

If both indices go out of bounds, we return true; otherwise, we return false. If any recursive path returns true, we immediately return true. This approach is exponential. Can you think of a way to optimize it?

Hint 4

We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

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

        def dfs(i, j):
            if j == n:
                return i == m

            match = i < m and (s[i] == p[j] or p[j] == ".")
            if (j + 1) < n and p[j + 1] == "*":
                return (dfs(i, j + 2) or          # don't use *
                       (match and dfs(i + 1, j))) # use *
            if match:
                return dfs(i + 1, j + 1)
            return False

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(2 ^ {m + n})$
Space complexity: $O(m + n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $p$ .

2. Dynamic Programming (Top-Down)

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

        def dfs(i, j):
            if j == n:
                return i == m
            if (i, j) in cache:
                return cache[(i, j)]

            match = i < m and (s[i] == p[j] or p[j] == ".")
            if (j + 1) < n and p[j + 1] == "*":
                cache[(i, j)] = (dfs(i, j + 2) or
                                (match and dfs(i + 1, j)))
                return cache[(i, j)]

            if match:
                cache[(i, j)] = dfs(i + 1, j + 1)
                return cache[(i, j)]

            cache[(i, j)] = False
            return False

        return dfs(0, 0)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $p$ .

3. Dynamic Programming (Bottom-Up)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [[False] * (len(p) + 1) for i in range(len(s) + 1)]
        dp[len(s)][len(p)] = True

        for i in range(len(s), -1, -1):
            for j in range(len(p) - 1, -1, -1):
                match = i < len(s) and (s[i] == p[j] or p[j] == ".")

                if (j + 1) < len(p) and p[j + 1] == "*":
                    dp[i][j] = dp[i][j + 2]
                    if match:
                        dp[i][j] = dp[i + 1][j] or dp[i][j]
                elif match:
                    dp[i][j] = dp[i + 1][j + 1]

        return dp[0][0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $p$ .

4. Dynamic Programming (Space Optimized)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [False] * (len(p) + 1)
        dp[len(p)] = True

        for i in range(len(s), -1, -1):
            nextDp = [False] * (len(p) + 1)
            nextDp[len(p)] = (i == len(s))

            for j in range(len(p) - 1, -1, -1):
                match = i < len(s) and (s[i] == p[j] or p[j] == ".")

                if (j + 1) < len(p) and p[j + 1] == "*":
                    nextDp[j] = nextDp[j + 2]
                    if match:
                        nextDp[j] |= dp[j]
                elif match:
                    nextDp[j] = dp[j + 1]

            dp = nextDp

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $p$ .

5. Dynamic Programming (Optimal)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [False] * (len(p) + 1)
        dp[len(p)] = True

        for i in range(len(s), -1, -1):
            dp1 = dp[len(p)]
            dp[len(p)] = (i == len(s))

            for j in range(len(p) - 1, -1, -1):
                match = i < len(s) and (s[i] == p[j] or p[j] == ".")
                res = False
                if (j + 1) < len(p) and p[j + 1] == "*":
                    res = dp[j + 2]
                    if match:
                        res |= dp[j]
                elif match:
                    res = dp1
                dp[j], dp1 = res, dp[j]

        return dp[0]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $p$ .