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 表示 true，0 表示 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. 建立二维数组 dp，dp[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*"，此时代表匹配了3次b。
        和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] 的情况呢，你这里只增加了 1 ，j = 0 时仍然会数组越界啊？实际上我们观察步骤4，dp[j - 2]只出现在 p[j] == '*' 的情况下，而 * 不可能是 p 的首元素的。

6. 数组 dp 的初始化。
   我们只需要对第一列和第一行进行初始化即可，其他地方均赋值为 false。我们的行和列都比原来增加了1，我们可以假设在 s 和 p 前面都加了一个字符'#'。
   例如 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 解法三：有限状态自动机

没学过，日后再更。