当前位置： 首页 > article >正文

LeetCode - 10 正则表达式匹配

article 2024/11/13 10:08:59

题目来源

10. 正则表达式匹配 - 力扣（LeetCode）

题目描述

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

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

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

示例 1

  • 输入：s = "aa", p = "a"
  • 输出：false
  • 解释："a" 无法匹配 "aa" 整个字符串。

示例 2

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

示例 3

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

提示

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

题目解析

解法一：套用内置正则表达式能力

本题需要我们实现一个正则匹配功能，其中 "." 和 "*" 的作用和正则表达式内元字符 "." 和 "*" 的作用一致。

因此，本题最简单的解法，就是直接套用编程语言的内置正则表达式能力。

本题需要我们实现的是完全匹配，因此如果套用内置正则能力的话，p 需要改造为 "^" + p + "$"。

C语言的正则表达式使用 regex.h 库，需要注意的是，regexec 函数的最后一个参数不能使用 REG_EXTENDED，而是需要使用 0。

关于 REG_EXTENDED 含义，可以参考下：c 正则表达式 - 小石王 - 博客园 (cnblogs.com)

 

什么是动态规划

所谓动态规划，即递推，从简单易解的小问题的结果，逐步递推出，复杂难解的大问题的结果。

分解过程：大问题逐步分解为相同类型小问题

比如 fibnaci 数列的求解：fibnaci(n) = fibnaci(n-1) + fibnaci(n - 2)

即，我们想要求fibnaci数列的第 n 个元素值，则可以分解为求解 fibnaci数列的第 n-1 和 n-2 个元素值。

按此逻辑一直分解下去的话，fibnaci(3) = fibnaci(2) + fibnaci(1)

fibnaci(2) 和 fibnaci(1) 无法再继续分解，而这两个元素又是简单易求的，即 fibnaci(2) = 1，fibnaci(1)=1。

递推过程：从小问题结果逐步递推出大问题结果

首先，已知了 fibnaci(1) 和 fibnaci(2) 的结果，那么就可以求出 fibnaci(3) = fibnaci(2) + fibnaci(1) 的结果

之后，已知了 fibnaci(2) 和 fibnaci(3) 的结果，那么就可以求出 fibnaci(4) = fibnaci(3) + fibnaci(2)的结果

....

最后，已知了 fibnaci(n-2) 和 fibnaci(n-1) 的结果，那么就可以求出 fibnaci(n) = fibnaci(n-1) + fibnaci(n-2) 的结果。

动态规划的难点

动态规划的难点在于：状态转移方程 的总结。

什么是状态转移方程呢？比如fibnaci数列求解公式：fibnaci(n) = fibnaci(n-1) + fibnaci(n-2)，就是一个状态转移方程。

即 fibnaci(n) 的结果（状态），可以从子问题 fibnaci(n-1) ， fibnaci(n-2) 的结果（状态）转移而来。

解法二：本题的动态规划解题思路

首先，我们要将本题的大问题："验证字符串s是否完全匹配模式串p"，进行分解，分解的思路就是："验证子串 s[0,i] 是否完全匹配模式子串 p[0,j] "

这样分解的话，只会降低问题规模，不会改变问题本质。

我们可以定义一个状态：dp[i][j] 来记录：子串 s[0,i] 是否完全匹配模式子串 p[0,j] 的结果。

若 子串 s[0,i] 完全匹配模式子串 p[0,j]，则dp[i][j] = true，否则 dp[i][j] = false。

接下来就是状态转移方程的推导：

如果 p[j] != '*'

  • 若 p[j] == s[i] || p[j] == '.'

    比如 s = "abb"，p = "ab"，此时 s, p     匹配结果等价于 s = "abb"，p = "ab"，即：dp[i][j] = dp[i-1][j-1]

    比如 s = "abb"，p = "ab."，此时 s,p 匹配结果等价于 s = "abb"，p = "ab."，即：dp[i][j] = dp[i-1][j-1]
  • 若 s[i] != p[j]，

    比如 s = "abb"，p = "abc"，则此时可以确定 s，p无法完全匹配，即：dp[i][j] = false

如果 p[j] == '*'，则此时 p[j] 代表一个量词符，用于修饰它前面的一个字符 p[j - 1] 出现0次或多次，即此时有两种情况：

  • 匹配0次，即我们可以忽略模式串 p 的 p[j-1] 和 p[j] 两个字符，比如下面例子

    s = "abb"，p = "abbc*"，此时 s, p 的匹配结果等价于 s = "abb"，p = "abbc*"
  • 匹配多次，比如下面例子

    s = "abbbbb"，p = "ab*"，此时红色部分是匹配的

需要注意的是，这两种情况只要有一种可以使得结果完全匹配，则最终结果就可以完全匹配。

关于 p[j] == '*' 时的状态转移方程的推导：

  • 匹配0次，dp[i][j] = dp[i][j-2]，即忽略了模式串p的 j-1 和 j 部分。
  • 匹配多次，有一个前提条件，那就是 p[j-1] == s[i] || p[j-1] == '.'，比如下面例子：

    s = "abbbb"，p = "ab*"

    s = "abbbb"，p = "a.*"

    满足这个前提条件的话，即可得下面状态转移方程：

    dp[i][j] = dp[i-1][j]

    这个状态转移方程什么意思呢？我们看一个例子：

    s = "abbbb"，p = "ab*"，此时 s, p 的匹配结果其实等价于：s = "abbbb"，p = "ab*"

    即此时我们可以忽略 s 串尾部已确认可以匹配的字符，因为它存在与否已经不影响匹配结果

以上就是所有情况的转台转移方程推导过程。

我们一开始定义了状态为 dp[i][j]，是一个二维数组，用来记录 s[0,i] 和 p[0,j] 的匹配结果。

按照上面分解思路，最终我们可以分解到 s[0,0] 和 p[0, 0] 这种简单子问题，但是这个子问题还是不够简单，因为需要我们去比较 s[0] 和 p[0]。

为了初始状态简单，我们可以为 s 和 p 加一个相同前缀，比如：

  • s = " " + s
  • p = " " + p

这样的话，s[0] 和 p[0] 就必然是匹配的，即dp[0][0] = true。同时这个增加前缀的行为，不会影响原始 s 和 p 的匹配结果，比如：

s = "abbb"，p = "ab*"，如果为 s, p 同时加一个空格前缀，那么 s = " abbb"，p = " ab*"，可以发现，匹配结果是不会收到影响的。

C源码实现

解法一：正则表达式解法
bool isMatch(char* s, char* p) {
    char pattern[30] = {'\0'};
    strcat(pattern, "^");
    strcat(pattern, p);
    strcat(pattern, "$");

    regex_t reg;
    regcomp(&reg, pattern, 0);

    return regexec(&reg, s, 0, NULL, 0) == 0;
}
解法二：动态规划
bool isMatch(char *s, char *p) {
    char tmpS[30] = {' '};
    char tmpP[30] = {' '};

    strcat(tmpS, s);
    strcat(tmpP, p);

    s = tmpS;
    p = tmpP;

    int n = strlen(s);
    int m = strlen(p);

    bool dp[n][m];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j] = false;
        }
    }

    dp[0][0] = true; // 空正则可以完全匹配空串

    for (int i = 0; i < n; i++) {
        char sTail = s[i];

        for (int j = 1; j < m; j++) { // 可能有人会有疑问, 不从0开始的话, 会不会影响 dp二维数组第0列 的状态推导，答案是不会的，因为 dp 第0列除了 dp[0][0]，其他的都默认是false, 因为空正则不能匹配非空串
            char pTail = p[j];

            if (pTail == '*') {
                char pTailBefore = p[j - 1];

                bool case1 = (pTailBefore == sTail || pTailBefore == '.') && i >= 1 && dp[i - 1][j];  // * 匹配多次
                bool case2 = j >= 2 && dp[i][j - 2]; // * 匹配0次

                dp[i][j] = case1 || case2;  // 注意, 匹配0次 和 匹配多次 只要有一个成立, 则最终结果成立
            } else {
                dp[i][j] = (pTail == sTail || pTail == '.') && i >= 1 && dp[i - 1][j - 1];  // 比如 s = "abb", p = "acb", 则此时 s,p 的匹配结果等价于：s = "ab", p = "ac"
            }
        }
    }

    return dp[n - 1][m - 1];
}

C++源码实现

解法一：正则表达式解法
class Solution {
public:
    bool isMatch(string s, string p) {
        regex reg("^" + p + "$");
        return regex_match(s, reg);
    }
};
解法二：动态规划
class Solution {
public:
    bool isMatch(string s, string p) {
        s = " " + s;
        p = " " + p;

        int n = s.length();
        int m = p.length();

        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
        dp[0][0] = true; // 空正则可以完全匹配空串

        for (int i = 0; i < n; i++) {
            char sTail = s[i];
            for (int j = 1; j < m; j++) {  // 可能有人会有疑问, 不从0开始的话, 会不会影响 dp二维数组第0列 的状态推导，答案是不会的，因为 dp 第0列除了 dp[0][0]，其他的都默认是false, 因为空正则不能匹配非空串
                char pTail = p[j];

                if (pTail == '*') {
                    char pTailBefore = p[j - 1];

                    bool case1 = (pTailBefore == sTail || pTailBefore == '.') && i >= 1 && dp[i - 1][j]; // * 匹配多次
                    bool case2 = j >= 2 && dp[i][j - 2];  // * 匹配0次

                    dp[i][j] = case1 || case2; // 注意, 匹配0次 和 匹配多次 只要有一个成立, 则最终结果成立
                } else {
                    dp[i][j] = (pTail == sTail || pTail == '.') && i >= 1 && dp[i - 1][j - 1];  // 比如 s = "abb", p = "acb", 则此时 s,p 的匹配结果等价于：s = "ab", p = "ac"
                }
            }
        }

        return dp[n - 1][m - 1];
    }
};

Java源码实现

解法一：正则表达式解法
class Solution {
    public boolean isMatch(String s, String p) {
        return s.matches("^" + p + "$");
    }
}
 解法二：动态规划
class Solution {
    public boolean isMatch(String s, String p) {
        s = " " + s;
        p = " " + p;

        int n = s.length();
        int m = p.length();

        boolean[][] dp = new boolean[n][m];
        dp[0][0] = true; // 空正则可以完全匹配空串

        for (int i = 0; i < n; i++) {
            char sTail = s.charAt(i);

            for (int j = 1; j < m; j++) { // 可能有人会有疑问, 不从0开始的话, 会不会影响 dp二维数组第0列 的状态推导，答案是不会的，因为 dp 第0列除了 dp[0][0]，其他的都默认是false, 因为空正则不能匹配非空串
                char pTail = p.charAt(j);

                if (pTail == '*') {
                    char pTailBefore = p.charAt(j - 1);

                    boolean case1 = (pTailBefore == sTail || pTailBefore == '.') && i >= 1 && dp[i - 1][j]; // * 匹配多次
                    boolean case2 = j >= 2 && dp[i][j - 2]; // * 匹配0次

                    dp[i][j] = case1 || case2; // 注意, 匹配0次 和 匹配多次 只要有一个成立, 则最终结果成立
                } else {
                    dp[i][j] = (pTail == sTail || pTail == '.') && i >= 1 && dp[i - 1][j - 1]; // 比如 s = "abb", p = "acb", 则此时 s,p 的匹配结果等价于：s = "ab", p = "ac"
                }
            }
        }

        return dp[n - 1][m - 1];
    }
}

Python源码实现

解法一：正则表达式解法
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if re.match("^" + p + "$", s):
            return True
        else:
            return False
解法二：动态规划
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        s = " " + s
        p = " " + p

        n = len(s)
        m = len(p)

        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True  # 空正则可以完全匹配空串

        for i in range(n):
            sTail = s[i]
            for j in range(1, m):  # 可能有人会有疑问, 不从0开始的话, 会不会影响 dp二维数组第0列 的状态推导，答案是不会的，因为 dp 第0列除了 dp[0][0]，其他的都默认是false, 因为空正则不能匹配非空串
                pTail = p[j]

                if pTail == '*':
                    pTailBefore = p[j - 1]

                    case1 = (pTailBefore == sTail or pTailBefore == '.') and i >= 1 and dp[i - 1][j]  # * 匹配多次
                    case2 = j >= 2 and dp[i][j - 2]  # * 匹配0次

                    dp[i][j] = case1 or case2  # 注意, 匹配0次 和 匹配多次 只要有一个成立, 则最终结果成立
                else:
                    dp[i][j] = (pTail == sTail or pTail == '.') and i >= 1 and dp[i - 1][j - 1]  # 比如 s = "abb", p = "acb", 则此时 s,p 的匹配结果等价于：s = "ab", p = "ac"

        return dp[n - 1][m - 1]

JavaScript源码实现

解法一：正则表达式解法
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    return new RegExp(`^${p}$`).test(s);
};
解法二：动态规划
/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
    s = " " + s;
    p = " " + p;

    const n = s.length;
    const m = p.length;

    const dp = new Array(n).fill(0).map(() => new Array(m).fill(false));
    dp[0][0] = true; // 空正则可以完全匹配空串

    for (let i = 0; i < n; i++) {
        const sTail = s[i];

        for (let j = 1; j < m; j++) { // 可能有人会有疑问, 不从0开始的话, 会不会影响 dp二维数组第0列 的状态推导，答案是不会的，因为 dp 第0列除了 dp[0][0]，其他的都默认是false, 因为空正则不能匹配非空串
            const pTail = p[j];

            if (pTail == '*') {
                const pTailBefore = p[j - 1];

                const case1 = (pTailBefore == sTail || pTailBefore == '.') && i >= 1 && dp[i - 1][j]; // * 匹配多次
                const case2 = j >= 2 && dp[i][j - 2]; // * 匹配0次

                dp[i][j] = case1 || case2; // 注意, 匹配0次 和 匹配多次 只要有一个成立, 则最终结果成立
            } else {
                dp[i][j] = (pTail == sTail || pTail == '.') && i >= 1 && dp[i - 1][j - 1];  // 比如 s = "abb", p = "acb", 则此时 s,p 的匹配结果等价于：s = "ab", p = "ac"
            }
        }
    }

    return dp[n - 1][m - 1];
};

http://www.kler.cn/a/290629.html

相关文章：

  • 使用docker-compose单点搭建社区版seafile+onlyoffice在线word编辑平台
  • Python酷库之旅-第三方库Pandas(208)
  • 云防护单节点2T抗攻击能力意味着什么？
  • 国标GB28181视频平台EasyCVR私有化部署视频平台对接监控录像机NVR时，录像机“资源不足”是什么原因？
  • 【Python特征工程系列】利用SHAP进行特征重要性分析-XGB模型为例（案例+源码）
  • 晨控RFID技术助力半导体制造业革新之路
  • C#文件的输入和输出
  • MATLAB生成COE文件
  • Java类和对象之构造方法与对象创建之计算数学中的分数值
  • 谈谈AI领域的认知误区、机会点与面临的挑战
  • 如何对 PDF 进行密码保护
  • 微服务架构下的服务治理实现方案详解
  • Nginx源码阅读1-内存池
  • Linux驱动（五）：Linux2.6驱动编写之设备树
  • 传统CV算法——图像基本操作与形态学操作
  • 【软件技巧】第35课，软件逆向安全工程师之汇编指令mov、ptr、xchg交换指令，每天5分钟学习逆向吧！
  • 枚举+数学，CF 449A - Jzzhu and Chocolate
  • AI科学家：自动化科研的未来之路
  • Java JAR命令打包详解与坑点
  • 【适配器】设计模式：旧系统迁移与第三方库集成的解决方案
  • ElasticSearch-聚合操作
  • 【大数据】浅谈Pyecharts：数据可视化的强大工具
  • MySQL数据库安装（详细）—＞Mariadb的安装（day21）
  • Linux教程8：文本编辑命令vi
  • css画个熊猫
  • 面试（九）