Keshawn_lu's Blog

Leetcode 10. 正则表达式匹配

动态规划
字数统计: 997阅读时长: 4 min
2020/06/20 Share

题目简介：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

1
2
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

思路：

又是一道看了解析也做的异常艰难的题…尽力把思路讲清楚吧

首先利用动态规划的思想，dp[i][j]代表s[0...i]和p[0...j]是否能匹配成功。

为了方便处理边界问题，两个字符串都先在开头加上一个空格，初始化dp[0][0] = true。

然后先初始化字符串s为空时，匹配的情况，也就是初始化dp[0][j]的值。只有当p[j] == '*'时，令p[j - 1]重复0次，也就是去掉p[j - 1], p[j]这两个字符，才有可能与空字符串匹配成功，此时dp[0][j] == dp[0][j - 2]。

然后开始循环遍历s与j字符串，会遇到以下这几种情况：

  1. p[j] != '*'时，若s[i] == p[j] || p[j] == '.'，那么当前字符是匹配成功的，所以dp[i][j] == dp[i - 1][j - 1]。
  2. p[j] == '*'时：
    1. 匹配0次，也就是将p[j - 1], p[j]都去除后能匹配成功，dp[i][j] == dp[i][j - 2]。
    2. 当p[j - 1] == '.' || p[j - 1] == s[i]时，则dp[i][j]取决于dp[i - 1][j]，因为在s最后加一个一样的字符也没有关系，即s[i] == s[i - 1]，因为*可以匹配任意个相同的字符。所以dp[i][j] == dp[i - 1][j]。(aaa与 aaa*是匹配的，也就是*使末尾的a重复一次：a* == a)
    3. 综合上面两种情况，dp[i][j] == zero || one。

最后返回dp[s.length() - 1][p.length() - 1]即可。

tip:

  • 开头加空格的方法很实用，利于代码的理解及后续操作。

代码如下：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    bool isMatch(string s, string p) {

        if(p.empty())
            return s.empty();

        vector<vector<bool>> dp(s.length() + 1, vector<bool>(p.length() + 1, false));

        //处理边界,加空格
        s = " " + s;
        p = " " + p;

        dp[0][0] = true;

        //初始化
        for(int j = 2; j < p.length(); j++){

            if(p[j] == '*'){

                dp[0][j] = dp[0][j - 2];
            }
        }

        for(int i = 1; i < s.length(); i++){

            for(int j = 1; j < p.length(); j++){

                if(s[i] == p[j] || p[j] == '.') //当前匹配成功
                    dp[i][j] = dp[i - 1][j - 1];

                if(p[j] == '*'){

                    bool zero;  //匹配0次
                    bool one;   //匹配1次

                    if(j - 2 >= 0){

                        zero = dp[i][j - 2];
                    }

                    //若dp[i - 1][j]已匹配成功，那么s[i] == s[i - 1]，即在最后加一个一样的也没有关系，因为*可以匹配任意个相同的字符
                    one = dp[i - 1][j] && (p[j - 1] == '.' || p[j - 1] == s[i]);
                    dp[i][j] = zero || one;

                }
            }
        }

        return dp[s.length() - 1][p.length() - 1];
        
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网