本文目录
1 中文题目
给一个字符串 s 和一个字符规律 p，实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
- ‘
.’ 匹配任意单个字符 - ‘
*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
示例 1：
- 输入：
s = "aa", p = "a" - 输出：
False - 解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = "aa", p = "a*"
输出：True
解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3：
输入：s = "ab", p = ".*"
输出：True
解释：“.*” 表示可匹配零个或多个（‘*’）任意字符（‘.’）。
提示：
- 1 ≤ s . l e n g t h ≤ 20 1 \leq s.length \leq 20 1≤s.length≤20
- 1 ≤ p . l e n g t h ≤ 20 1 \leq p.length \leq 20 1≤p.length≤20
s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
2 求解思路
2.1 基础解法：递归法
思路
将问题分解为更小的子问题，每次处理一个字符。对于每个位置，检查当前字符是否匹配，然后根据下一个字符是否为’*'来决定如何递归处理剩余部分。
算法详细步骤：
- 定义递归函数，参数为两个指针i和j，分别指向s和p的当前位置
- 处理基本情况（模式串结束）
- 检查当前字符是否匹配（相等或为’.'）
- 处理特殊情况（下一个字符是’*'）
- 处理普通字符匹配
- 递归处理剩余部分
python代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
"""
使用递归实现正则表达式匹配
参数:
s: 待匹配的字符串
p: 模式串
返回:
是否匹配成功
"""
def match(i: int, j: int) -> bool:
"""
递归匹配函数
参数:
i: 字符串当前位置
j: 模式串当前位置
返回:
s[i:]和p[j:]是否匹配
"""
# 基本情况1：模式串到达末尾
if j == len(p):
# 字符串也必须到达末尾才算匹配成功
return i == len(s)
# 检查当前字符是否匹配
# first_match为True的条件：
# 1. 字符串未到末尾
# 2. 当前字符相等或模式字符为'.'
first_match = (i < len(s) and
(s[i] == p[j] or p[j] == '.'))
# 特殊情况：处理'*'
if j + 1 < len(p) and p[j + 1] == '*':
return (
# 情况1：跳过x*模式（匹配0次）
match(i, j + 2) or
# 情况2：当前字符匹配，尝试匹配下一个字符（匹配1次或多次）
(first_match and match(i + 1, j))
)
# 普通情况：当前字符匹配后移动两个指针
return first_match and match(i + 1, j + 1)
# 从两个字符串的开头开始匹配
return match(0, 0)
时空复杂度分析
- 时间复杂度分析：
- 最坏情况：O(2^n)，n为字符串长度。每个位置可能需要尝试两种选择（使用或不使用’*'）
- 空间复杂度分析：
- 递归调用栈：O(n+m)，n为字符串长度，m为模式串长度
2.2 优化解法：动态规划和递归结合
思路
使用递归的方式自顶向下解决问题，但用一个记忆化数组/哈希表存储已经计算过的状态，避免重复计算。遇到相同的子问题时直接返回已存储的结果。
- 核心思想：
- 将大问题分解为子问题：s[i:]和p[j:]是否匹配
- 用(i,j)表示当前正在匹配的位置
- 记录已解决的子问题避免重复计算
- 状态定义：
- dp(i,j) 表示 s[i:] 能否匹配 p[j:]
- i 是字符串s的当前位置
- j 是模式串p的当前位置
- 状态转移分析：
情况1：当前字符直接匹配（p[j]不是'*'）
- 检查s[i]和p[j]是否匹配
- 如果匹配，问题转化为dp(i+1, j+1)
- 如果不匹配，返回False
情况2：下一个字符是'*'（p[j+1]是'*'）
- 匹配0次：跳过当前模式和'*'，dp(i, j+2)
- 匹配多次：当前匹配成功后保持模式不变，dp(i+1, j)
Python代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
"""
动态规划和递归结合（记忆化搜索）解决正则匹配
参数:
s: 待匹配的字符串
p: 模式串
返回:
布尔值，表示是否匹配成功
"""
# 创建记忆化数组，存储中间计算结果
memo = {}
def dp(i: int, j: int) -> bool:
"""
递归函数，判断s[i:]和p[j:]是否匹配
参数:
i: s的当前位置
j: p的当前位置
返回:
布尔值，表示是否匹配
"""
# 如果已经计算过，直接返回结果
if (i, j) in memo:
return memo[(i, j)]
# 如果模式串到达末尾，检查字符串是否也到达末尾
if j == len(p):
ans = i == len(s)
else:
# 检查当前字符是否匹配
# 条件：字符串未结束 且 (字符相等 或 模式字符为'.')
first_match = (i < len(s) and
(s[i] == p[j] or p[j] == '.'))
# 处理'*'的情况
if j + 1 < len(p) and p[j + 1] == '*':
ans = (
# 匹配0次：跳过当前模式字符和'*'
dp(i, j + 2) or
# 匹配1次或多次：当前字符匹配，保持模式不变
(first_match and dp(i + 1, j))
)
else:
# 普通字符匹配：当前字符匹配则继续往后匹配
ans = first_match and dp(i + 1, j + 1)
# 存储计算结果
memo[(i, j)] = ans
return ans
# 从字符串和模式串的开头开始匹配
return dp(0, 0)
时空复杂度分析
- 时间复杂度：O(mn)
- m是s的长度，n是p的长度
- 每个状态只计算一次
- 空间复杂度：O(mn)
- 记忆化数组大小
- 递归调用栈深度
2.3 最优解法：NFA（非确定性有限自动机）
思路
将正则表达式转换为非确定性有限自动机，通过构建状态转移图来实现匹配。
- 对于普通字符直接转移
- 对于’*'创建两个ε转移（跳过或重复）
- 对于’.'接受任意字符转移。
使用集合维护当前所有可能的状态。
python代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
"""
使用NFA（非确定性有限自动机）实现正则表达式匹配
参数:
s: 待匹配的字符串
p: 模式串
返回:
是否匹配成功
"""
# 构建NFA的状态转移图
class State:
"""状态节点类"""
def __init__(self):
# 字符转移：key是字符，value是目标状态
self.trans = {}
# epsilon转移：不消耗输入字符的转移
self.eps = set()
# 是否为接受状态
self.is_end = False
def build_nfa() -> State:
"""
构建NFA
返回：起始状态
"""
# 创建起始状态
start = State()
# 当前状态
cur = start
# 创建所有状态节点
states = [start]
i = 0
while i < len(p):
if i + 1 < len(p) and p[i + 1] == '*':
# 处理 x* 模式
next_state = State()
states.append(next_state)
# 创建epsilon转移（跳过整个x*模式）
cur.eps.add(next_state)
# 创建循环转移（匹配x多次）
loop_state = State()
states.append(loop_state)
if p[i] == '.':
# .* 可以匹配任意字符
loop_state.trans['any'] = loop_state
else:
# x* 只能匹配特定字符
loop_state.trans[p[i]] = loop_state
# 设置epsilon转移
cur.eps.add(loop_state)
loop_state.eps.add(next_state)
cur = next_state
i += 2
else:
# 处理普通字符
next_state = State()
states.append(next_state)
if p[i] == '.':
cur.trans['any'] = next_state
else:
cur.trans[p[i]] = next_state
cur = next_state
i += 1
# 设置接受状态
cur.is_end = True
return start
def get_epsilon_closure(state: State, visited: set) -> set:
"""
计算epsilon闭包（所有通过epsilon转移可达的状态）
"""
if state in visited:
return set()
visited.add(state)
states = {state}
for next_state in state.eps:
states.update(get_epsilon_closure(next_state, visited))
return states
def match(s: str) -> bool:
"""
执行NFA匹配过程
"""
# 构建NFA
start = build_nfa()
# 当前可能的状态集合
current_states = get_epsilon_closure(start, set())
# 处理每个输入字符
for c in s:
next_states = set()
# 对当前每个状态进行转移
for state in current_states:
# 处理普通转移
if c in state.trans:
next_states.add(state.trans[c])
# 处理通配符转移
if 'any' in state.trans:
next_states.add(state.trans['any'])
# 计算所有可达状态的epsilon闭包
current_states = set()
for state in next_states:
current_states.update(get_epsilon_closure(state, set()))
# 如果没有可达状态，匹配失败
if not current_states:
return False
# 检查是否存在接受状态
return any(state.is_end for state in current_states)
return match(s)
时空复杂度分析
- 时间复杂度分析：O(m*n)
- NFA构建：O(m)，m为模式串长度
- 状态转移：O(n*k)，n为输入串长度，k为NFA中状态数量（最坏情况下为m）
- 空间复杂度分析：O(m)
- 状态图存储：O(m)
当前状态集合：O(m)
- 状态图存储：O(m)
3 题目总结
题目难度：困难
数据类型：字符串
应用算法： 递归、动态规划、NFA