How do I solve the Regular Expression Matching problem?

Use dynamic programming to build a table that checks all possible matches between substrings of the string and pattern, considering the special characters '.' and '*'.

What is the time complexity of solving Regular Expression Matching?

The time complexity is O(m * n), where `m` is the length of the string and `n` is the length of the pattern.

What is the role of '*' in the Regular Expression Matching?

'*' matches zero or more occurrences of the preceding character in the pattern, allowing flexibility in matching repetitive characters.

How does state transition dynamic programming apply here?

State transition dynamic programming helps solve the problem by systematically transitioning through the states of substrings of `s` and `p` to verify a match.

Can I solve Regular Expression Matching without dynamic programming?

While possible, solving the problem without dynamic programming would result in inefficient recursive solutions, leading to high time complexity due to repeated subproblem evaluations.

#10

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

正则表达式匹配

给你一个字符串 s 和一个字符规律 p ，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素返回一个布尔值，表示匹配是否覆盖整个输入字符串（而非部分）。示例 1：输入： s = "aa", p = "a" 输出： fal…

字符串动态规划递归

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

返回一个布尔值，表示匹配是否覆盖整个输入字符串（而非部分）。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j)$ ，表示从 $s$ 的第 $i$ 个字符开始，和 $p$ 的第 $j$ 个字符开始是否匹配。那么答案就是 $dfs(0, 0)$ 。

函数 $dfs(i, j)$ 的计算过程如下：

如果 $j$ 已经到达 $p$ 的末尾，那么如果 $i$ 也到达了 $s$ 的末尾，那么匹配成功，否则匹配失败。
如果 $j$ 的下一个字符是 '*'，我们可以选择匹配 $0$ 个 $s[i]$ 字符，那么就是 $dfs(i, j + 2)$ 。如果此时 $i \lt m$ 并且 $s[i]$ 和 $p[j]$ 匹配，那么我们可以选择匹配 $1$ 个 $s[i]$ 字符，那么就是 $dfs(i + 1, j)$ 。
如果 $j$ 的下一个字符不是 '*'，那么如果 $i \lt m$ 并且 $s[i]$ 和 $p[j]$ 匹配，那么就是 $dfs(i + 1, j + 1)$ 。否则匹配失败。

过程中，我们可以使用记忆化搜索，避免重复计算。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是 $s$ 和 $p$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        @cache
        def dfs(i, j):
            if j >= n:
                return i == m
            if j + 1 < n and p[j + 1] == '*':
                return dfs(i, j + 2) or (
                    i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j)
                )
            return i < m and (s[i] == p[j] or p[j] == '.') and dfs(i + 1, j + 1)

        m, n = len(s), len(p)
        return dfs(0, 0)

speed

复杂度分析

指标	值
时间	Let
空间	The only memory we use is the

psychology

面试官常问的追问

外企场景

question_mark
Assess understanding of dynamic programming, especially with state transitions.
question_mark
Check if the candidate can handle special cases like empty strings or patterns with consecutive '*' and '.' characters.
question_mark
Evaluate the candidate’s ability to optimize recursive solutions using memoization.

warning

常见陷阱

外企场景

error
Failing to handle edge cases like empty string `s` or pattern `p` properly.
error
Not correctly implementing the handling of '*' to match zero occurrences of the preceding character.
error
Overcomplicating the solution without leveraging dynamic programming or recursion effectively.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to match the pattern with case sensitivity or allow more complex special characters.
arrow_right_alt
Solve the problem with a greedy approach instead of dynamic programming.
arrow_right_alt
Modify the problem to check for partial string matching rather than complete string matching.

help

常见问题

外企场景

继续练习

#44 通配符匹配 #241 为运算表达式设计优先级 #5 最长回文子串