Jiez19971225‘s Blog

做自己爱做的事

0%

leetcodeP10-RegularExpressionMatching

发表于 更新于 分类于   |   字数统计: 543(字)   |   阅读时长: 2(分)

这一题最开始想到模拟，也想到了匹配的贪婪问题，感觉题目可能不要求那么多，结果是 WA，看到讨论区 PO 出的一份代码，使用了动态规划，想了一下确实改用 DP，此题确有一定难度，在此记录一下解法。

题目描述

给你一个字符串 s 和字符串 p，s 只包含英文小写字母，p 只包含英文小写字母和 ‘.’ 或 ‘*‘，实现一个支持元字符 ‘.’ 和 ‘*‘的正则匹配

解题思路

设 dp[x][y]表示取字符串 s 前 x 个字符和模式串 p 前 y 个字符是否能够完全匹配，为一个 bool 值
初始状态 dp[0][0] = true，若 p 串以”a*b*c*“的形式开头，则 dp[0][2],dp[0][4],dp[0][6]也为 true，显示这种状态是匹配的
dp 的转移过程为
若 s[i-1] == p[j-1] || p[j-1] == ‘.’，dp[i][j] = dp[i][j] || dp[i-1][j-1]
若 p[j-1] == ‘*‘ ，方程至多可从一下三种状态转移

  • dp[i][j] = dp[i][j] || dp[i][j-2]，*可以匹配 0 个多个，因此总可以从该状态转移
  • 若 s[i-1] == p[j-2] || int(p[j-2]) == ‘.’，即匹配 “?*“形式，可采用贪婪与非贪婪策略
    • dp[i][j] = dp[i][j] || dp[i-1][j] ，采用非贪婪策略，*不匹配字符
    • dp[i][j] = dp[i][j] || dp[i][j-1]，采用贪婪策略，*匹配字符

以下是代码，参考了 leetcode 上的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func isMatch(s string, p string) bool {
    lens := len(s)
    lenp := len(p)
    var dp [][]bool

    for i := 0; i <= lens; i++ {
        d := make([]bool, lenp+1)
        dp = append(dp, d)
    }
    dp[0][0] = true
    for j := 1; j <= lenp; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-2]
        }
    }

    for i := 1; i <= lens; i++ {
        for j := 1; j <= lenp; j++ {
            if s[i-1] == p[j-1] || p[j-1] == '.' {
                dp[i][j] = dp[i][j] || dp[i-1][j-1]
            } else if p[j-1] == '*' {
                dp[i][j] = dp[i][j] || dp[i][j-2]
                if s[i-1] == p[j-2] || int(p[j-2]) == '.' {
                    dp[i][j] = dp[i][j] || dp[i-1][j]
                    dp[i][j] = dp[i][j] || dp[i][j-1]
                }
            }
        }
    }
    return dp[lens][lenp]
}