【LeetCode】10. 正则表达式匹配

10. 正则表达式匹配

题目描述

给你一个字符串 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.length <= 20
• 1 <= p.length <= 20
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

解题思路

这道题要求实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配器。这是一个经典的字符串匹配问题，需要处理复杂的模式匹配逻辑。

算法分析

这道题的核心思想是动态规划状态转移，主要解法包括：

1. 动态规划方法：使用二维DP表记录匹配状态（推荐）
2. 递归方法：带备忘录的递归实现
3. 优化版本：减少空间复杂度的DP实现
4. 回溯方法：不使用备忘录的递归实现

问题本质分析

动态规划详解

flowchart TDA[创建DP表] --> B[初始化边界条件]B --> C[填充DP表]C --> D[返回最终结果]B --> E[dp[0][0] = true]B --> F[处理模式串开头的*号]C --> G[遍历字符串和模式串]G --> H{当前字符匹配?}H -->|是| I[dp[i][j] = dp[i-1][j-1]]H -->|否| J{当前模式是*号?}J -->|是| K[处理*号匹配]J -->|否| L[dp[i][j] = false]K --> M[匹配0次: dp[i][j-2]]K --> N[匹配多次: dp[i-1][j]]I --> O[继续下一位置]L --> OM --> P[dp[i][j] = dp[i][j-2]]N --> Q[dp[i][j] = dp[i][j] || dp[i-1][j]]P --> OQ --> OO --> R{还有位置?}R -->|是| GR -->|否| D

DP表填充过程

星号处理策略

graph TDA[星号处理] --> B[匹配0次]A --> C[匹配1次]A --> D[匹配多次]B --> E[跳过当前字符和星号]C --> F[匹配当前字符]D --> G[继续匹配相同字符]E --> H[dp[i][j] = dp[i][j-2]]F --> I[dp[i][j] = dp[i-1][j-2]]G --> J[dp[i][j] = dp[i-1][j]]H --> K[状态转移]I --> KJ --> K

各种解法对比

算法流程图

flowchart TDA[开始] --> B[创建DP表]B --> C[初始化边界条件]C --> D[i = 1, j = 1]D --> E{i <= m?}E -->|否| F[返回dp[m][n]]E -->|是| G{j <= n?}G -->|否| H[i++, j = 1]G -->|是| I{当前字符匹配?}I -->|是| J[dp[i][j] = dp[i-1][j-1]]I -->|否| K{当前模式是*号?}K -->|是| L[处理*号匹配]K -->|否| M[dp[i][j] = false]L --> N[匹配0次: dp[i][j-2]]N --> O[匹配多次: dp[i-1][j]]O --> P[dp[i][j] = dp[i][j] || dp[i-1][j]]J --> Q[j++]M --> QP --> QQ --> GH --> EF --> R[结束]

边界情况处理

时间复杂度分析

空间复杂度分析

关键优化点

实际应用场景

测试用例设计

代码实现要点

1. DP表设计：

   • dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
   • 需要处理空字符串和空模式的边界情况

2. 星号处理：

   • 匹配0次：dp[i][j] = dp[i][j-2]
   • 匹配多次：dp[i][j] = dp[i-1][j]
   • 需要检查前一个字符是否匹配

3. 状态转移：

   • 普通字符：dp[i][j] = dp[i-1][j-1]
   • 通配符：dp[i][j] = dp[i-1][j-1]
   • 星号：复杂的组合逻辑

4. 边界条件：

   • dp[0][0] = true（空字符串匹配空模式）
   • 处理模式串开头的*号情况
   • 字符串为空时的特殊处理

5. 空间优化：

   • 只保存当前行和前一行
   • 使用滚动数组减少空间复杂度

这个问题的关键在于理解动态规划的状态转移逻辑和正确处理星号的各种匹配情况，通过构建DP表记录所有可能的匹配状态，实现高效的正则表达式匹配。

完整题解代码

package mainimport ("fmt"
)// isMatch 正则表达式匹配 - 动态规划方法
// 时间复杂度: O(m*n)，其中m和n分别是字符串和模式串的长度
// 空间复杂度: O(m*n)
func isMatch(s string, p string) bool {m, n := len(s), len(p)// 创建DP表，dp[i][j]表示s的前i个字符与p的前j个字符是否匹配dp := make([][]bool, m+1)for i := range dp {dp[i] = make([]bool, n+1)}// 空字符串与空模式匹配dp[0][0] = true// 处理模式串开头的*号情况for j := 1; j <= n; j++ {if p[j-1] == '*' {dp[0][j] = dp[0][j-2]}}// 填充DP表for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if p[j-1] == '.' || p[j-1] == s[i-1] {// 当前字符匹配dp[i][j] = dp[i-1][j-1]} else if p[j-1] == '*' {// 处理*号dp[i][j] = dp[i][j-2] // 匹配0次if p[j-2] == '.' || p[j-2] == s[i-1] {dp[i][j] = dp[i][j] || dp[i-1][j] // 匹配1次或多次}}}}return dp[m][n]
}// isMatchRecursive 递归方法 - 带备忘录
// 时间复杂度: O(m*n)
// 空间复杂度: O(m*n)
func isMatchRecursive(s string, p string) bool {memo := make(map[string]bool)return matchHelper(s, p, 0, 0, memo)
}func matchHelper(s, p string, i, j int, memo map[string]bool) bool {key := fmt.Sprintf("%d,%d", i, j)if val, exists := memo[key]; exists {return val}// 如果模式串已经用完if j == len(p) {result := i == len(s)memo[key] = resultreturn result}// 如果字符串已经用完if i == len(s) {// 检查剩余的模式是否都是x*的形式if (len(p)-j)%2 == 1 {memo[key] = falsereturn false}for k := j; k < len(p); k += 2 {if p[k] != '*' {memo[key] = falsereturn false}}memo[key] = truereturn true}// 当前字符是否匹配currentMatch := i < len(s) && (p[j] == '.' || p[j] == s[i])var result boolif j+1 < len(p) && p[j+1] == '*' {// 处理*号：匹配0次或多次result = matchHelper(s, p, i, j+2, memo) || // 匹配0次(currentMatch && matchHelper(s, p, i+1, j, memo)) // 匹配多次} else {// 普通匹配result = currentMatch && matchHelper(s, p, i+1, j+1, memo)}memo[key] = resultreturn result
}// isMatchOptimized 优化版本 - 减少空间复杂度
// 时间复杂度: O(m*n)
// 空间复杂度: O(n)
func isMatchOptimized(s string, p string) bool {m, n := len(s), len(p)// 只使用一维DP数组dp := make([]bool, n+1)// 初始化第一行dp[0] = truefor j := 1; j <= n; j++ {if p[j-1] == '*' {dp[j] = dp[j-2]}}// 逐行填充for i := 1; i <= m; i++ {prev := dp[0]dp[0] = falsefor j := 1; j <= n; j++ {temp := dp[j]if p[j-1] == '.' || p[j-1] == s[i-1] {dp[j] = prev} else if p[j-1] == '*' {dp[j] = dp[j-2] // 匹配0次if p[j-2] == '.' || p[j-2] == s[i-1] {dp[j] = dp[j] || dp[j] // 匹配多次}} else {dp[j] = false}prev = temp}}return dp[n]
}// isMatchBacktrack 回溯法 - 不使用备忘录
// 时间复杂度: 最坏情况O(2^(m+n))
// 空间复杂度: O(m+n)
func isMatchBacktrack(s string, p string) bool {return backtrackHelper(s, p, 0, 0)
}func backtrackHelper(s, p string, i, j int) bool {// 如果模式串已经用完if j == len(p) {return i == len(s)}// 如果字符串已经用完if i == len(s) {// 检查剩余的模式是否都是x*的形式if (len(p)-j)%2 == 1 {return false}for k := j; k < len(p); k += 2 {if p[k] != '*' {return false}}return true}// 当前字符是否匹配currentMatch := i < len(s) && (p[j] == '.' || p[j] == s[i])if j+1 < len(p) && p[j+1] == '*' {// 处理*号：匹配0次或多次return backtrackHelper(s, p, i, j+2) || // 匹配0次(currentMatch && backtrackHelper(s, p, i+1, j)) // 匹配多次} else {// 普通匹配return currentMatch && backtrackHelper(s, p, i+1, j+1)}
}func main() {// 测试用例1s1 := "aa"p1 := "a"result1 := isMatch(s1, p1)fmt.Printf("示例1: s = \"%s\", p = \"%s\"\n", s1, p1)fmt.Printf("输出: %t\n", result1)fmt.Printf("期望: false\n")fmt.Printf("结果: %t\n", result1 == false)fmt.Println()// 测试用例2s2 := "aa"p2 := "a*"result2 := isMatch(s2, p2)fmt.Printf("示例2: s = \"%s\", p = \"%s\"\n", s2, p2)fmt.Printf("输出: %t\n", result2)fmt.Printf("期望: true\n")fmt.Printf("结果: %t\n", result2 == true)fmt.Println()// 测试用例3s3 := "ab"p3 := ".*"result3 := isMatch(s3, p3)fmt.Printf("示例3: s = \"%s\", p = \"%s\"\n", s3, p3)fmt.Printf("输出: %t\n", result3)fmt.Printf("期望: true\n")fmt.Printf("结果: %t\n", result3 == true)fmt.Println()// 额外测试用例s4 := "aab"p4 := "c*a*b"result4 := isMatch(s4, p4)fmt.Printf("额外测试: s = \"%s\", p = \"%s\"\n", s4, p4)fmt.Printf("输出: %t\n", result4)fmt.Printf("期望: true\n")fmt.Printf("结果: %t\n", result4 == true)fmt.Println()s5 := "mississippi"p5 := "mis*is*p*."result5 := isMatch(s5, p5)fmt.Printf("额外测试: s = \"%s\", p = \"%s\"\n", s5, p5)fmt.Printf("输出: %t\n", result5)fmt.Printf("期望: false\n")fmt.Printf("结果: %t\n", result5 == false)fmt.Println()// 测试递归版本fmt.Println("=== 递归版本测试 ===")result1Rec := isMatchRecursive(s1, p1)result2Rec := isMatchRecursive(s2, p2)fmt.Printf("递归版本示例1: %t\n", result1Rec)fmt.Printf("递归版本示例2: %t\n", result2Rec)fmt.Printf("结果一致: %t\n", result1Rec == result1 && result2Rec == result2)fmt.Println()// 测试优化版本fmt.Println("=== 优化版本测试 ===")result1Opt := isMatchOptimized(s1, p1)result2Opt := isMatchOptimized(s2, p2)fmt.Printf("优化版本示例1: %t\n", result1Opt)fmt.Printf("优化版本示例2: %t\n", result2Opt)fmt.Printf("结果一致: %t\n", result1Opt == result1 && result2Opt == result2)fmt.Println()// 测试回溯版本fmt.Println("=== 回溯版本测试 ===")result1Back := isMatchBacktrack(s1, p1)result2Back := isMatchBacktrack(s2, p2)fmt.Printf("回溯版本示例1: %t\n", result1Back)fmt.Printf("回溯版本示例2: %t\n", result2Back)fmt.Printf("结果一致: %t\n", result1Back == result1 && result2Back == result2)fmt.Println()// 边界值测试fmt.Println("=== 边界值测试 ===")boundaryTests := []struct {s, p string}{{"", ""},     // 空字符串{"", "a*"},   // 空字符串与模式{"a", ""},    // 字符串与空模式{"a", "a"},   // 单字符匹配{"a", "."},   // 单字符与通配符{"a", "a*"},  // 单字符与星号{"a", ".*"},  // 单字符与任意星号{"aa", "a"},  // 双字符与单字符{"aa", "a*"}, // 双字符与星号{"aa", ".*"}, // 双字符与任意星号{"ab", "a*"}, // 不同字符与星号{"ab", ".*"}, // 不同字符与任意星号}for _, test := range boundaryTests {result := isMatch(test.s, test.p)fmt.Printf("s = \"%s\", p = \"%s\", result = %t\n", test.s, test.p, result)}
}