Leetcode 10. 正则表达式匹配

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 Falseif p[j]==".":return Trueelif p[j]==s[i]:return Trueelse:return Falsefor 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]=Falseelse: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.执行结果

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/442291.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

k8s的控制节点不能访问node节点容器的ip地址

master控制node服务器添加容器后,访问不了该node服务器容器的ip,只能在node服务器访问 排查后发现是k8s的master服务器和node节点的网址网段和k8s初始化时提示的ip网段不一致 我之前是192.168.137.50, 实际上master主机期望的是192.168.1.50 解决方案: 1.删除服务器后重建ma…

python爬虫 - 进阶requests模块

&#x1f308;个人主页&#xff1a;https://blog.csdn.net/2401_86688088?typeblog &#x1f525; 系列专栏&#xff1a;https://blog.csdn.net/2401_86688088/category_12797772.html 目录 前言 一、SSL证书问题 &#xff08;一&#xff09;跳过 SSL 证书验证 &#xff0…

Vue3中提到的Tree-shaking

我们知道&#xff0c;Vue3中提到一个叫Tree-shaking的东西&#xff0c;其实也并不是一个新的东西&#xff0c;有人称之为"摇树优化"&#xff0c;什么意思&#xff1f; 按照作者的原话解释&#xff0c;Tree-shaking其实就是&#xff1a;把无用的模块进行“剪枝”&…

【Linux】进程间通信——System V消息队列和信号量

一、消息队列 1.1 概念 进程间通信的原理是让不同进程看到同一份资源&#xff0c;资源种类的不同就决定了通信方式的差异。如果用管道通信&#xff0c;则资源是文件缓冲区&#xff1b;如果用共享内存&#xff0c;则资源是内存块 消息队列是由操作系统提供的资源&#xff0c;…

postman自动化实战总结

Postman实战总结 简介 本次实战内容主要包括如下几点&#xff1a; l 背景介绍 l Postman使用&#xff0c;侧重于自动化实现&#xff0c;基础使用不做介绍 l 可视化Newman介绍 l 框架特色 l 实战中的坑 背景 随着国内软件技术的高速发展&#xff0c;越来越多的手工测试…

解决谷歌浏览器在安卓手机上的常见问题

在使用安卓手机浏览网页时&#xff0c;谷歌浏览器无疑是许多用户的首选。然而&#xff0c;在使用过程中&#xff0c;用户可能会遇到一些常见问题&#xff0c;如搜索图片困难、缓存积累过多导致浏览器卡顿&#xff0c;以及无法下载视频等。本文将针对这些问题&#xff0c;提供详…

【Linux】详解Linux下的工具(内含yum指令和vim指令)

文章目录 前言1. Linux下软件安装的方式2. yum2.1 软件下载的小知识2.2 在自己的Linux系统下验证yum源的存在2.3 利用yum指令下载软件2.4 拓展yum源&#xff08;针对于虚拟机用户&#xff09; 3. vim编辑器3.1 vim是什么&#xff1f;3.2 如何打开vim3.2 vim各模式下的讲解3.2.1…

【C语言】猜数字小游戏

&#x1f602;个人主页: 起名字真南 &#x1f923;个人专栏:【数据结构初阶】 【C语言】 【C】 目录 1 随机数的生成1.1 rand1.2 srand1.3 time1.4 设置随机数范围 2 猜数字游戏实现 前言&#xff1a;我们学习完前面的循环以后可以写一个猜数字小游戏 1 随机数的生成 想要完成…

新生培训 day1 C语言基础 顺序 分支 循环 数组 字符串 函数

比赛地址 b牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ C语言数据类型 字符 整型数 int 2e9 long long 9e18 浮点数 代码示例 /** Author: Dduo * Date: 2024-10-8* Description: 新生培训day1 */ #include <stdio.h>int main() {// 定义变量in…

QT-空窗口主窗口对话框

1. QMainWindow QMainWindow 用来创建主窗口 主窗口包含&#xff1a; 标题栏&#xff08;Window title&#xff09;、菜单栏&#xff08;MenuBar&#xff09;、工具栏&#xff08;ToolBar&#xff09;、状态栏&#xff08;StatusBar&#xff09;、停靠部件&#xff08;DockWid…

Ansible学习之ansible-pull命令

想要知道ansible-pull是用来做什么的&#xff0c;就需要了解Ansible的工作模&#xff0c;Ansible的工作模式有两种&#xff1a; push模式 push推送&#xff0c;这是Ansible的默认模式&#xff0c;在主控机上编排好playbook文件&#xff0c;push到远程主机上来执行。pull模式 p…

RISC-V知识点目录

分支预测 分支预测概述https://blog.csdn.net/zhangshangjie1/article/details/136947089?sharetypeblogdetail&sharerId136947089&sharereferPC&sharesourcezhangshangjie1&spm1011.2480.3001.8118分支指令的方向预测https://blog.csdn.net/zhangshangjie1/a…

如何革新源代码保密?七大方法教你应对!

在数字化时代&#xff0c;源代码的安全保密对于企业而言至关重要&#xff0c;它不仅关系到企业的核心竞争力&#xff0c;还涉及到知识产权的保护。源代码一旦泄露&#xff0c;可能会给企业带来无法估量的损失。因此&#xff0c;采取有效的源代码保密措施&#xff0c;是每个企业…

【电路】1.3 电功率和能量

1.3 电功率和能量 电是一种能量存在形式。 1.3.1 电压的定义 将单位正电荷由A点移动至B点&#xff0c;电场力所做的功是 w w w&#xff0c;则 u A B d w d q u_{AB}\frac{dw}{dq} uAB​dqdw​&#xff0c; w w w是功&#xff0c; q q q是电荷量从A到B&#xff0c;沿着任意路…

D3.js中国地图可视化

1、项目介绍 该项目来自Github&#xff0c;基于D3.js中国地图可视化。 D3.js is a JavaScript library for manipulating documents based on data. It uses HTML, SVG, and CSS to display data. The full name of D3 is "Data-Driven Documents," which means it a…

C++11--列表初始化和声明

统一的列表初始化 { } 初始化 C11引入了统一的 列表初始化&#xff08;Uniform Initialization&#xff09;&#xff0c;这是一种使用大括号 { } 初始化变量和对象的新语法&#xff0c;旨在简化初始化过程并提高代码的可读性和一致性。 这种初始化方式适用于几乎所有类型&am…

轻松掌握IP代理服务器设置方法,网络冲浪更自如

在数字化时代&#xff0c;互联网就像是一片浩瀚的海洋&#xff0c;而IP代理服务器就如同我们在这片海洋中航行的指南针。通过使用代理IP&#xff0c;我们可以更方便地访问全球网络资源&#xff0c;提升网络安全性。本文将为您详细介绍IP代理服务器的设置方法&#xff0c;让您在…

Library介绍(四)

标准单元描述 标准单元主要由以下几个部分构成&#xff0c;分别是引脚电容、power、timing组成。其中引脚电容主要包含input/output pin的电容值。 power主要包含每个pin的leakage power和internal power。 timing主要包括cell的input pin到output pin的rise delay和fall del…

人才画像系统是什么?有哪些功能和作用?

人才画像系统是一种先进的人力资源管理工具&#xff0c;它运用大数据和人工智能技术对员工的多方面特征进行深度分析。系统通过汇聚个人的教育背景、工作经验、技能掌握、性格特质及行为数据等信息&#xff0c;结合数据挖掘和机器学习算法&#xff0c;构建出每位员工的数字化“…

Spring Boot:打造下一代医院管理系统

3系统分析 3.1可行性分析 通过对本医院管理系统实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本医院管理系统采用JAVA作为开发语言&#xff0c;Spring Boot框…