LeetCode(C++)刷题计划:10-正则表达式匹配

10-正则表达式匹配

@Author:CSU张扬
@Email:csuzhangyang@gmail.com or csuzhangyang@qq.com

1. 题目

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

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

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

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *
示例 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 = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/regular-expression-matching

2. 解法

2.1 解法一:递归法

参考:Joy

  1. p为空。s为空,则返回true;s不为空,则返回false。

  2. 当p的第二个元素是 * 时,有两种情况,满足一种就可以:

    (1):剔除p中前两个元素,再来判断是否匹配。
    例如:s = "aab", p = "c*a*b"。其中 c* 可以是0个c,所以可以无视掉。
    直接判断s = "aab"p = "a*b"是否匹配。
    (2):当 s[0] == p[0] || p[0] == '.' 时,剔除s中第一个元素,再来判断是否匹配。
    例如:s = "aab", p = "a*b"a*可以匹配0~多个,s[0] = 'a'被匹配,可以删除。接下来比较s = "ab"p = "a*b"是否匹配。

  3. 如果第二个元素不是 *,那就只能是 a-z 或者 '.' 了。
    当第一个元素两两匹配时,我们就可以删除掉这俩元素了,因为没有 *的情况下,a-z'.'只能匹配一次。
    例如:s = "aab", p = ".a*b"。因为 p[1] = 'a', p[0] = s[0] = 'a'。所以剔除掉首元素,接下来判断s = "ab", p = "a*b"是否匹配。

执行用时: 300 ms, 在所有 cpp 提交中击败了29.78%的用户
内存消耗: 15.5 MB, 在所有 cpp 提交中击败了14.56%的用户

class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty())
            return s.empty();
        if (p.size() > 1 && p[1] == '*')
            return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
        else
            return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
    }
};

2.2 解法二:动态规划

参考:乔碧萝殿下❤Krahets

dp数组的样子: s="abb",p="ab*c*",方便大家理解。
为什么加 '#' 见步骤5。
1 表示 true0 表示 false

  # a b * c *
# 1 0 0 0 0 0
a 0 1 0 1 0 1
b 0 0 1 1 0 1
b 0 0 0 1 0 1
  1. 建立二维数组 dpdp[i][j] 表示 s 的前 i 个元素和 p 的前 j 个元素是否匹配。

  2. 首先分析最简单的情况:s[i] == p[j]。此时若s的前i-1个元素和p的前j-1个元素相匹配,那么s的前i个元素和p的前j个元素也必相匹配。即此时的状态转移方程为: dp[i][j] = dp[i - 1][j - 1]

  3. 第二种情况,当 p[j] == '.' 时,和2中情况相同,状态转移方程仍为:dp[i][j] = dp[i - 1][j - 1]

  4. 第三种比较复杂的情况,当 p[j] == '*'时。此时我们必须要考虑 '*' 之前的元素,分为以下两种情况:

    1. s[i] != p[j - 1]dp[i][j] = dp[i][j - 2],此时表示 * 前面的字母根本和 s[i] 中字母不相同。
      例如: s = "abb", p = "ab*c*",对于p中第二个 * 来说,其前面的字母c满足这种情况,c*相当于匹配了0次c,相当于直接剔除 c*,是否匹配取决于s = "abb", p = "ab*"
    2. s[i] == p[j - 1] || p[j] == '.',此时表示匹配上了,但是不知道匹配了几次。
      • 匹配多次: dp[i][j] = dp[i-1][j]
        例如:s = "abbb", p = "ab*",此时代表匹配了3b
        s = "abb", p = "ab*的匹配状态相同,继而又和s = "ab", p = "ab*的匹配状态相同。
      • 匹配一次:dp[i][j] = dp[i][j - 1]
        例如:s = "ab", p = "ab*"。若s = "ab", p = "ab匹配,那么它肯定也匹配。
      • 匹配零次:dp[i][j] = dp[i][j - 2]
        例如:s = "ab", p = "abc*",对于c来说匹配了0次,那么c*就没有什么意义,也就可以剔除掉c*
  5. 考虑边界值的问题。
    因为如果当 i=0 时,dp[i][j] = dp[i - 1][j - 1]就会数组越界。这里我们的处理办法是行和列各增加一个维度,即: dp[m + 1][n + 1]
    这时读者可能会有疑问,还有 dp[j - 2] 的情况呢,你这里只增加了 1j = 0 时仍然会数组越界啊?实际上我们观察步骤4,dp[j - 2]只出现在 p[j] == '*' 的情况下,而 * 不可能是 p 的首元素的。

  6. 数组 dp 的初始化。
    我们只需要对第一列第一行进行初始化即可,其他地方均赋值为 false。我们的行和列都比原来增加了1,我们可以假设在 sp 前面都加了一个字符'#'
    例如 s = "#abb", p = "#ab*c*",那么dp的第一行就是代表 s[0]p 的前 j 个元素是否匹配。此时 dp[0][0] = true,因为 s[0] = p[0] = '#'

    1. 第一行的初始化:
      因为我们的 p 始终和 '#'进行匹配判断,并且 p[0] = '#' ,那么后面只要出现了 '*',那它肯定匹配了0次;单独出现 a-z 或者 '.' 肯定无法与 s[0] = '#' 匹配,因为 p 首元素就是 #
    2. 第一列的初始化:
      例如 s = "#abb", p = "#ab*c*",那么dp的第一行就是 p[0]s 的前 i 个元素是否匹配。我们可以看出,只有 p[0] = s[0] = '#' 是匹配的,其他地方都不匹配。
      '#''#' 匹配。
      '#''#a' 不匹配。
      '#''#ab' 也不匹配。
      '#''#abb' 也不匹配。

    下面举两个例子方便大家理解初始化规则,只需看第一列和第一行即可。
    初始化例子1:s = "#abb", p = "#ab*c*"时:

      # a b * c *
    # 1 0 0 0 0 0
    a 0 1 0 1 0 1
    b 0 0 1 1 0 1
    b 0 0 0 1 0 1
    

    初始化例子2:s = "#abb", p = "#a*b*c*"时:

      # a * b * c *
    # 1 0 1 0 1 0 1
    a 0 1 1 0 1 0 1
    b 0 0 0 1 1 0 1
    b 0 0 0 0 1 0 1
    

执行用时: 4 ms, 在所有 cpp 提交中击败了98.13%的用户
内存消耗: 8.4 MB, 在所有 cpp 提交中击败了91.48%的用户

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        bool dp[m + 1][n + 1];
        // 初始化
        for (auto &i : dp)
            for (auto &j : i)
                j = false;
        dp[0][0] = true;
        for (auto j = 0; j < n; ++ j) {
            if (p[j] == '*')
                dp[0][j + 1] = dp[0][j - 1];
        }
        for (auto i = 0; i < m; ++ i) {
            for (auto j = 0; j < n; ++ j) {
                if (s[i] == p[j] || p[j] == '.')
                    dp[i + 1][j + 1] = dp[i][j];
                else if (p[j] == '*') {
                    if (s[i] != p[j - 1] && p[j - 1] != '.')
                        dp[i + 1][j + 1] = dp[i + 1][j - 1];
                    else
                         dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j] || dp[i + 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

2.3 解法三:有限状态自动机

没学过,日后再更。

上一篇:ABB.RobotWare数据包 下载分享


下一篇:ABB PM802F