算法刷题笔记 - 正则表达式的匹配

发表于 更新于 阅读次数：

正则表达式匹配

  • 来源 : LeetCode - 正则表达式匹配
  • 难度 : 困难
  • 标签 : 动态规划

    题目描述

    给你一个字符串s和一个字符规律p，请你来实现一个支持 ‘.’ 和 ‘*‘ 的正则表达式匹配。
    • ‘.’ 匹配任意单个字符
    • ‘*‘ 匹配零个或多个前面的那一个元素
      所谓匹配，是要匹配整个字符串s, 而不是部分字符串。

例子:

  • “mississippi”和”mis*is*p*.”不匹配
  • “aab”和”c*a*b”匹配
  • 特别的”.*“可匹配任意字符串

解法构思

有关串匹配应想到利用动态规划

  • 此题中的p和s没有位置对应关系, 因为p的组成元素可能一个字符, 可能是一个字符加上’*‘, 为了使p和s有一定的位置对应关系, 即是p中的每一个元素占一个位置, 即令p为p忽略’*‘的序列, 另外构建star表, 表示每个位置的字符是否可重复，可为1，反之为0。接下来，就是解决 **s和p** 的匹配问题，与以前的通配符匹配的那道题极其类似。
  • 定义规划表
    首先确定应是二维表，又考虑到空串的匹配，行列数应该是字符串s和匹配串p的长度加一，即定义DP[0:m+1][0:n+1]。DP[i][j] 代表s的前i个字符构成的串与p的前j个字符构成的串是否匹配, 匹配为1, 不匹配为0

  • 构建转移方程

  • 考虑DP[i][j]，

    • 定义:
      • 当前匹配，是s[0:i - 1]（包含s[i - 1]字符）与p[0:j - 1]（包含p[i - 1]字符）的匹配，
      • s的当前字符，是s[i-1],
      • p_的当前字符，是p_[j-1],
      • 字符的“重复”，是指 “字符*“
    • 如果star[j - 1] == 0，即匹配串当前字符没有“可重复”（即星号）标记，
      • 如果s[i - 1] == p_[j - 1]，应DP[i][j] = DP[i - 1][j - 1]，即字符串与匹配串的尾字符相等, 是否匹配即取决于二者除去尾字符后的匹配情况。
        • 如果p_[j - 1] == ‘.’, 应DP[i][j] = DP[i - 1][j - 1]，匹配串的尾字符为’.’, 即对字符串尾字符没要求, 即是否匹配即取决于二者除去尾字符后的匹配情况。
    • 如果star[j - 1] == 1，即匹配串当前字符有“可重复”（即星号）标记，
      • 如果p[j - 1] == s[i - 1] 或者 p[j - 1] == ‘.’, 应DP[i][j] = DP[i][j - 1] || DP[i - 1][j] ，则说明当前字符相匹配，则该考虑的是，p_的当前字符的“重复”匹配的是一个字符还是多个字符。
        1. 如果此“重复”仅匹配一个字符, 则当此时 s 能与 p_除去尾字符 后匹配时当前匹配成功；
        2. 如果此“重复”匹配多个字符，即当 s除去最后字符 后仍能与 p_[0:j - 1] 匹配时当前匹配成功。
      • 如果p[j - 1] != s[i - 1]并且匹配串当前字符（p[j - 1]）不是’.’，应DP[i][j] = DP[i][j - 1]，,即匹配串当前字符的 “重复” 对应空串(即’*‘代表的重复0次的情况)，即当此时 s 能与 p_除去尾字符 后匹配时当前匹配成功；
        • 其他情况 : DP[i][j] = 0
    • 考虑边界情况
      • 两空串一定可匹配, 即DP[0][0] = 1
      • 一个空的匹配串不能匹配任何串, 即DP[i][0] = 0, i = 1, 2, … ,len(s)
      • 一个空串只能被全部由“重复”构成的匹配串匹配, 即DP[0][j] = 1, j = 1, 2, …, p_的全部由“重复”构成的最大前缀的长度

    上手编程

    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
    bool isMatch(string s, string p) {
        const int M = s.size();   
        
        string p_;  // 去除'*'后的p
        vector<char> star;  // 是否重复

        p.push_back('$');  // 增加哨兵
        
        //  构建p_
        for (int i = 0; i < p.size() - 1; ++i) {
            p_.push_back(p[i]);
            if (p[i + 1] == '*') {
                ++i;
                star.push_back(1);
            } else star.push_back(0);
        }
        
        const int N = p_.size();
        
        // 定义DP表
        vector<vector<char>> dp(M + 1, vector<char>(N + 1, 0));
        
        // 处理边界情况
        dp[0][0] = 1;
        for (int i = 1; i <= N && star[i - 1] == 1; ++i)
            dp[0][i] = 1;
        
        // 构建DP表
        for (int i = 1; i <= M; ++i) {
            for (int j = 1; j <= N; ++j) {
            
                if (star[j - 1] == 0) {
                    if (p_[j - 1] == '.' || p_[j - 1] == s[i - 1]) dp[i][j] = dp[i - 1][j - 1];
                    
                } else {
                    if (p_[j - 1] == '.'|| p_[j - 1] == s[i - 1])
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                    else dp[i][j] = dp[i][j - 1];
                }
            }
        }
        
        //  dp[M][N]即为结果
        return dp.back().back();
    }