正则表达式匹配

Regular Expression Matching

问题：正则表达式匹配

考察：字符串、动态规划、递归

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/regular-expression-matching

Problem: Regular Expression Matching

Patterns: String, Dynamic Programming, Recursion

Recency: 2yr

Link: https://leetcode.com/problems/regular-expression-matching

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：二维 DP，dp[i][j] 表示 s 前 i 个字符能否匹配 p 前 j 个字符。普通字符和 . 直接匹配前一状态；遇到 * 时可表示零个前字符，或在当前字符匹配时继续消费 s。

复杂度：时间 O(mn)，空间 O(mn)。