首页 > 其他分享 >Leetcode 10. 正则表达式匹配

Leetcode 10. 正则表达式匹配

时间:2024-10-07 11:11:25浏览次数:9  
标签:10 匹配 字符 正则表达式 状态 最后 字符串 Leetcode dp

1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/regular-expression-matching/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

在这里插入图片描述

第一步,状态定义;dp[i][j]为s的前i个字符串和p的前j个字符串是否匹配

第二步,状态初始化。初始化当匹配字符串为空时的匹配状态(即j=0时的状态),因为除了原字符串为空时,dp[0][0]=True,其余的情况下dp[x][0]=False,所以只需要初始化dp[0][0]=True即可

第三步,状态转移。当判断前i个字符和前j个匹配字符是否匹配时,这里先预先定义俩字符匹配为匹配字符为.或者匹配字符和原字符两者相等。

  • 如果最后一个匹配字符为号,并且倒数第二个匹配字符和原字符串最后一个字符匹配,可以选择让匹配一次,去除当前s子串中匹配的部分,此时的状态转移为dp[i][j]=dp[i-1][j],当选择让*匹配0个,则去除匹配子串中的x*组合,此时状态转移为dp[i][j]=dp[i][j-2];
  • 如果最后一个匹配字符为*,并且倒数第二个匹配字符和原字符串最后一个字符不匹配,则只能选择让*匹配0次,此时dp[i][j]=dp[i][j-2];
  • 如果最后一个匹配字符不为*号,并且该匹配字符与原字符串中最后一个字符匹配,此时的转移方程为dp[i][j]=dp[i-1][j-1];
  • 如果最后一个匹配字符不为*号,并且该匹配字符与原字符串最后一个字符不匹配,则当前的原字符串和匹配字符串一定无法匹配,即dp[i][j]=False。

经过遍历,最终的dp[sLen][pLen]即为题解

3.解题代码

Python代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        sLen,pLen=len(s),len(p)
        # 第一步,状态定义;dp[i][j]为s的前i个字符串和p的前j个字符串是否匹配
        dp=[[False]*(pLen+1) for i in range(sLen+1)]
        # 第二步,状态初始化。初始化当匹配字符串为空时的匹配状态(即j=0时的状态),因为除了原字符串为空时,dp[0][0]=True,其余的情况下dp[x][0]=False,所以只需要初始化dp[0][0]=True即可
        dp[0][0]=True   # 两个都是空字符串时,匹配
        # 第三步,状态转移。当判断前i个字符和前j个匹配字符是否匹配时,这里先预先定义俩字符匹配为匹配字符为.或者匹配字符和原字符两者相等。如果最后一个匹配字符为*号,并且倒数第二个匹配字符和原字符串最后一个字符匹配,可以选择让*匹配一次,去除当前s子串中匹配的部分,此时的状态转移为dp[i][j]=dp[i-1][j],当选择让*匹配0个,则去除匹配子串中的x*组合,此时状态转移为dp[i][j]=dp[i][j-2];如果最后一个匹配字符为*,并且倒数第二个匹配字符和原字符串最后一个字符不匹配,则只能选择让*匹配0次,此时dp[i][j]=dp[i][j-2];如果最后一个匹配字符不为*号,并且该匹配字符与原字符串中最后一个字符匹配,此时的转移方程为dp[i][j]=dp[i-1][j-1];如果最后一个匹配字符不为*号,并且该匹配字符与原字符串最后一个字符不匹配,则当前的原字符串和匹配字符串一定无法匹配,即dp[i][j]=False。经过遍历,最终的dp[sLen][pLen]即为题解
        # > 判断s[i]字符和p的p[j]字符是否匹配
        def match(i,j):
            if i<0 or j<0:
                return False
            if p[j]==".":
                return True
            elif p[j]==s[i]:
                return True
            else:
                return False
        for i in range(sLen+1):
            for j in range(1,pLen+1):
                if p[j-1]!="*":
                    if match(i-1,j-1):
                        dp[i][j]=dp[i-1][j-1]
                    else:
                        dp[i][j]=False
                else:
                    if match(i-1,j-2):
                        dp[i][j]=dp[i-1][j] or dp[i][j-2]
                    else:
                        dp[i][j]=dp[i][j-2]
        # print(dp[sLen][pLen])
        return dp[sLen][pLen]

C++代码

class Solution {
public:
    bool match(int i,int j,string s,string p){
        if(i<0 || j<0){
            return false;
        }
        if(p[j]=='.'){
            return true;
        }else if(p[j]==s[i]){
            return true;
        }else{
            return false;
        }
    }
    bool isMatch(string s, string p) {
        int sLen=s.size(),pLen=p.size();
        vector<vector<bool>> dp(sLen+1,vector<bool>(pLen+1,false));
        dp[0][0]=true;
        for(int i=0;i<sLen+1;++i){
            for(int j=1;j<pLen+1;++j){
                if(p[j-1]!='*'){
                    if(match(i-1,j-1,s,p)){
                        dp[i][j]=dp[i-1][j-1];
                    }else{
                        dp[i][j]=false;
                    }
                }else{
                    if(match(i-1,j-2,s,p)){
                        dp[i][j]=dp[i-1][j] || dp[i][j-2];
                    }else{
                        dp[i][j]=dp[i][j-2];
                    }
                }
            }
        }
        return dp[sLen][pLen];
    }
};

4.执行结果

在这里插入图片描述

标签:10,匹配,字符,正则表达式,状态,最后,字符串,Leetcode,dp
From: https://www.cnblogs.com/geek0070/p/18449833

相关文章

  • 20241006
    BacktoSchool'24P1-Kicking按照题意模拟即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+5;intn,m,k;charc;vector<int>sum[2][N];vector<int>a[N];signedmain(){cin>>......
  • 上周热点回顾(9.30-10.6)
    热点随笔:· 基于DPAPI+RDP技术实现本地打开远程程序,并映射到本地机器桌面上 (WeskyNet)· 只写后台管理的前端要怎么提升自己 (我不吃饼干呀)· C#/.NET/.NETCore技术前沿周刊|第7期(2024年9.23-9.30) (追逐时光者)· 10款好用的开源HarmonyOS工具库 (威哥爱编程)·......
  • Gym 100543G Virus synthesis 题解
    Solution首先只考虑回文串的答案;我们重点考虑的是偶回文串结论:对于偶回文串\(u\),从其最长的长度小于等于他的一半的回文后缀,或其父亲转移过来,一定是最优的证明:设\(u\)的一个回文子串为\(v\)(不是父亲),你要让\(v\tou\)的转移最优首先\(v\)不能跨过\(u\)的中点,因为此......
  • 一本通 1071:菲波那契数
    【题目描述】菲波那契数列是指这样的数列:数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。给出一个正整数k,要求菲波那契数列中第k个数是多少。【输入】输入一行,包含一个正整数k。(1≤k≤46)【输出】输出一行,包含一个正整数,表示菲波那契数列中第k个数的大小......
  • The 10th Shandong Provincial Collegiate Programming Contest
    A-Sekiro题意初始有\(n\)个金币,死了\(m\)次,死一次\(n=\lceil\fracn2\rceil\)。求最后的金币数。思路模拟。代码点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ intn,m; cin>>n>>m; while(m--......
  • 684. 冗余连接(leetcode)
    https://leetcode.cn/problems/redundant-connection/classSolution{publicint[]findRedundantConnection(int[][]edges){//思路:遍历边,不断的加入相连的点到集合中,直到遍历到同在一集合的两个顶点位置,这个边就可以是答案init(edges.length);......
  • Navicat连接数据库遭遇1045错误:如何解决及预防措施
    遇到Navicat连接MySQL数据库时出现 1045 错误(访问被拒绝,用户名或密码错误),可以通过以下几个步骤来解决和预防这个问题:解决方法确认用户名和密码确认在Navicat中输入的用户名和密码是否正确。可以尝试在MySQL命令行中验证用户名和密码是否正确。重置密码如果......
  • 2024.10.6训练记录
    下午cfA到!B签到题,考场还是写挂了,今天码力差。挂在while动指针的时候没有判右边界,似。唐诗程度不亚于数组开小。C1猜出来结论是第一次出现需要按照一开始的顺序就能过。C2把一开始的排列映射到[1,n]。修改时用set动态维护每个数第一次出现的位置。把第一次出现位置的......
  • 10.5牛客CSP-S考试总结
    10.5牛客CSP-S考试总结为什么牛客不允许我:main(){}T1看到题目感觉是道规律题,就把题目给的式子写出来,跑了几十组随机数据,发现好像是恒等式,于是直接大胆猜测任选三个数都可以满足等式。T2题面数学公式有点诈骗,求自然常数的多个自然对数相加的和的次方,形式化的求\(e^{\ln\......
  • Day10-JavaDoc
    Day10-JavaDocJavaDoc介绍JavaDoc:javadoc命令是用来生成自己API文档的。javadoc是一个工具,它可以读取源代码中的文档注释,并将其转换为格式规范的API文档。javadoc通过解析文档注释中的特定标记,如@author、@version、@since、@param、@return、@throws等,来提取关键信......