leetcode 剑指 Offer 19. 正则表达式匹配

题目描述

剑指 Offer 19. 正则表达式匹配

请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:

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

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

输入:
s = "aab"
p = "cab"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:
s = "mississippi"
p = "misisp*."
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ''。

解题思路

法1

使用动态规划来解决问题。

最后的整个字符串是否匹配取决于前面的字符串是否匹配,并且最后一个字符是否匹配,如果前面的字符串都匹配,并且最后一个字符串也匹配,那么就匹配成功,否则就失败

我们可以使用动态规划来获取前一个的匹配状态,

具体来说，我们使用一个二维数组 dp 来记录已经匹配的字符串和模式的状态。其中 dp[i][j] 表示字符串的前 i 个字符和模式的前 j 个字符是否匹配。

初始状态是 dp[0][0] = true，表示空字符串和空模式是匹配的。接下来，我们需要考虑一些特殊情况。

将*与其前面的字符看成一个整体

如果模式的第一个字符是 *，则我们可以将其和它前面的字符视为一个整体，表示这个字符可以出现 0 次。因此，我们有 dp[0][j] = dp[0][j-2]，表示空字符串和模式的前 j 个字符是否匹配。

接下来，我们通过两个循环来遍历字符串和模式的所有子串。如果当前的字符匹配，即 s[i-1] == p[j-1] 或者 p[j-1] == '.'，那么我们可以将 dp[i][j] 设置为 dp[i-1][j-1]，表示当前的子串匹配情况和之前的子串匹配情况相同。如果当前的模式字符是 *，我们需要考虑两种情况。一种是当前的字符可以出现 0 次，即 dp[i][j] = dp[i][j-2]。另一种是当前的字符可以出现多次，即 dp[i][j] = dp[i-1][j]，这里需要注意的是，当前的字符必须和前面的字符相同，或者前面的字符是 .。

最终，我们返回 dp[m][n]，表示整个字符串和模式是否匹配。其中 m 和 `

时间复杂度(O(nm))
空间复杂度(O(nm))

执行结果

法1

func isMatch(s string, p string) bool {
    m, n := len(s), len(p)
    dp := make([][]bool, m+1)
    for i := 0; i <= m; i++ {
        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]
        }
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s[i-1] == p[j-1] || p[j-1] == '.' {
                dp[i][j] = dp[i-1][j-1]
            } else if p[j-1] == '*' {
                if s[i-1] == p[j-2] || p[j-2] == '.' {
                    dp[i][j] = dp[i][j-2] || dp[i-1][j]
                } else {
                    dp[i][j] = dp[i][j-2]
                }
            }
        }
    }
    return dp[m][n]
}

执行结果：
通过
显示详情
查看示例代码
添加备注

执行用时：
0 ms
, 在所有 Go 提交中击败了
100.00%
的用户
内存消耗：
2.2 MB
, 在所有 Go 提交中击败了
79.37%
的用户
通过测试用例：
448 / 448
炫耀一下:

法2

法3

本文由mdnice多平台发布