当前位置: 首页 > news >正文

【Leetcode】10. 正则表达式匹配

10. 正则表达式匹配(困难)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  1. 题解

    • 如果从左向右进行匹配的话,需要考虑字符后是否有 * 。

      在这里插入图片描述

    • 因此选择从右向左扫描更为简单。

      *前面肯定有一个字符,它像是一个拷贝器,能够复制前面的单个字符,甚至也可以把这个字符消除(出现 0 次)。

      两个字符串是否匹配,取决于最右边的字符是否匹配,以及剩余的子串是否匹配。其中,「剩余的子串是否匹配」,就是本道题的子问题

      在这里插入图片描述

    • 状态定义:定义 dp[i][j] 为第一个字符串到 i 为止,第二个字符串到 j 为止,两个字符串是否匹配。如果匹配,dp[i][j] = true;如果不匹配,dp[i][j] = false

    • 子问题的考虑

      • 情况一:s[i-1] 和 p[j-1] 匹配,即 s[i-1] == p[j-1] || p[j-1] == '.'。那么只需要考虑剩余的子串是否匹配,即 dp[i][j] = dp[i-1][j-1];

        在这里插入图片描述

      • 情况二:s[i-1] 和 p[j-1] 不匹配。这时候不能直接认为两个字符串不匹配,而是需要进一步考虑 p[j-1] == '*' 的情况。但是如果不是 * ,那么肯定不匹配。

        在这里插入图片描述

        对于 * ,它可以匹配 0 个或多个字符。当s[i-1] 和 p[j-2] 匹配,且 p[j-1] == ‘*’ 时,需要考虑三种情况: * 使 dp[j-2] 出现 0 次、1 次或 >=2次。只要其中一种情况能使得两个子串匹配,我们就可以继续考虑剩余子串是否匹配。状态转移方程为:dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];

        在这里插入图片描述
        当s[i-1] 和 p[j-2] 不匹配,且 p[j-1] == ‘*’ 时,可以利用 * 消除不匹配字符 p[j-2],考虑 s[i-1] 和 p[j-3] 是否匹配。状态转移方程为:dp[i][j] = dp[i][j-2];

    • 初始情况:当两个字符串都是空串的时候,一定匹配,因此 dp[0][0] = true; ;当 s 为空时,如果 p 的右端字符是 * ,那么就可以使得 p 也变成空串;当 p 为空,两个字符串一定不匹配。

  2. 代码

    class Solution {
    public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));// 两个空字符串一定匹配dp[0][0] = true;// 如果s为空串 p[j-1]=* 也能够匹配for(int j=1; j<=n; ++j){if(p[j-1] == '*'){dp[0][j] = dp[0][j-2];}}// 从右向左匹配for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){// s[i-1]和p[j-1]匹配if(s[i-1] == p[j-1] || p[j-1] == '.'){dp[i][j] = dp[i-1][j-1];}// s[i-1]和p[j-1]不匹配else{// p[j-1] == '*' 且 s[i-1]和p[j-2]匹配if(p[j-1] == '*'){dp[i][j] = dp[i][j-2];if(s[i-1] == p[j-2] || p[j-2] == '.'){dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];}}}}}return dp[m][n];}
    };
    
  3. 收获

    • 理解错了 * 的意思,* 类似于一个拷贝器 ,能匹配前一个元素,也能消除前一个元素(匹配零个)。
    • 这道题需要考虑多种情况,感觉很难想得这么全面。

相关文章:

【Leetcode】10. 正则表达式匹配

10. 正则表达式匹配&#xff08;困难&#xff09; 题解 如果从左向右进行匹配的话&#xff0c;需要考虑字符后是否有 * 。 因此选择从右向左扫描更为简单。 *前面肯定有一个字符&#xff0c;它像是一个拷贝器&#xff0c;能够复制前面的单个字符&#xff0c;甚至也可以把这个…...

不得不说的结构型模式-装饰器模式

目录 装饰器模式是什么 下面是装饰器模式的一个通用的类图&#xff1a; 以下是使用C实现装饰器模式的示例代码&#xff1a; 下面是面试中关于桥接器模式的常见的问题&#xff1a; 下面是问题的答案&#xff1a; 装饰器模式是什么 装饰器模式是一种结构型设计模式&#xff…...

Flutter+YesAPI 快速构建零运维的APP

前言 移动互联网经过多年的发展&#xff0c;已经进入一个成熟的阶段&#xff0c;几乎每个公司都有自己的移动应用程序或移动网站。随着5G技术的不断发展&#xff0c;也带来了更高效的数据传输速度和更稳定的网络连接&#xff0c;这使得更多的应用程序和服务能够在互联网上运行&…...

使用Socks5代理保障HTTP传输的网络安全

一、引言 在互联网时代&#xff0c;网络安全越来越受到人们的关注&#xff0c;特别是在数据传输过程中&#xff0c;很容易出现信息泄露、窃听等安全问题。为了保障网络传输的安全性&#xff0c;我们可以使用代理服务器来进行传输&#xff0c;而Socks5代理是其中一种常用的代理…...

C语言入门篇——操作符篇

目录 1、操作符分类 2、操作符的属性 3、算术操作符 4、移位操作符 5、位操作符 6、赋值操作符 7、单目操作符 8、关系操作符 9、逻辑操作符 10、条件操作符 11、逗号操作符 12、下标引用、函数调用和结构成员 1、操作符分类 算术操作符&#xff08;&#xff0c;-&…...

YOLOv7训练自己的数据集(txt文件,笔记)

目录 1.代码下载 2.数据集准备&#xff08;.xml转.txt) &#xff08;1&#xff09;修改图像文件名 &#xff08;2&#xff09;图片和标签文件数量不对应&#xff0c;解决办法 &#xff08;3&#xff09;.xml转.txt &#xff08;4&#xff09;.txt文件随机划分出对应的训练…...

防止机械/移动硬盘休眠 - NoSleepHD

防止机械/移动硬盘休眠 - NoSleepHD 前言解决方案计算机硬盘移动硬盘 前言 机械硬盘休眠后唤醒需要一定时间&#xff0c;且频繁的启动和停止并不有利于硬盘的寿命&#xff0c;因此可根据自身需求防止机械硬盘休眠&#xff0c;下文以Win10系统为例介绍解决方案。 值得一提的是…...

(二)app自动化脚本录制回放

上一篇&#xff1a;(一)app自动化测试环境搭建&#xff08;maciosairtest &#xff09;_airtest环境搭建_要开朗的spookypop的博客-CSDN博客 注&#xff1a;后续都是用IOS设备来介绍自动化测试&#xff0c;安卓就不赘述了。 接上一篇&#xff0c;搭建好自动化测试环境后&#…...

STM32HAL库USART外设配置流程及库函数讲解

HAL库中USART外设配置流程及库函数讲解 一说到串口通信&#xff0c;及必须说一下aRS-232/485协议。232协议标准物理接口就是我们常用的DB9串口线 RS-232电平&#xff1a; 逻辑1&#xff1a;-15~-3 逻辑0&#xff1a; 3~15 COMS电平&#xff1a; 逻辑1&#xff1a;3.3 逻辑0&a…...

Qt 实现TCP通信和UDP通信

Qt 实现TCP通信和UDP通信 1、TCP通信 QT中实现TCP通信主要用到了以下类&#xff1a;QTcpServer、QTcpSocket、QHostAddress等&#xff1b; 使用QTcpServer来创建一个TCP服务器&#xff0c;在新的连接建立时&#xff0c;将新建立连接的socket添加到列表中&#xff0c;以便发送…...

完成近4亿元C轮融资+自研底盘域控,本土线控制动玩家“拼”了

显然&#xff0c;线控制动赛道已经进入白热化竞争阶段。 高工智能汽车研究院监测数据显示&#xff0c;2022年中国市场&#xff08;不含进出口&#xff09;乘用车前装搭载线控制动系统&#xff08;One-Box&#xff0c;Two-Box&#xff09;上险交付合计497.39万辆&#xff0c;同…...

【UE】一个简易的游戏计时器

效果 步骤 1. 打开“ThirdPersonGameMode” 创建两个整型变量&#xff0c;分别命名为“Seconds”、“Minutes” 在事件图表中添加如下节点&#xff0c;实现“Seconds”每秒加1 继续添加如下节点&#xff1a; 当秒数大于60时&#xff0c;就让分钟数1&#xff0c;然后将秒数重新…...

Leetcode力扣秋招刷题路-0455

从0开始的秋招刷题路&#xff0c;记录下所刷每道题的题解&#xff0c;帮助自己回顾总结 455. 分发饼干 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#x…...

一小时学会CSS (上)

1、CSS是什么&#xff1f; CSS &#xff08;Cascading Style Sheets&#xff09;层叠样式表&#xff0c;是一种来为结构化文档&#xff0c;例如HTML 、XML 添加字体&#xff0c;间距和颜色等样式的计算机语言,扩展名是.CSS 。 2、CSS语法规则 CSS写在哪里&#xff0c;CSS写在…...

DockerImage镜像版本说明

参考文章 1、https://medium.com/swlh/alpine-slim-stretch-buster-jessie-bullseye-bookworm-what-are-the-differences-in-docker-62171ed4531d 2、https://stackoverflow.com/questions/52083380/in-docker-image-names-what-is-the-difference-between-alpine-jessie-stret…...

ROS学习第三十三节——Arbotix使用

https://download.csdn.net/download/qq_45685327/87718484 1.介绍 通过 URDF 结合 rviz 可以创建并显示机器人模型&#xff0c;不过&#xff0c;当前实现的只是静态模型&#xff0c;如何控制模型的运动呢&#xff1f;在此&#xff0c;可以调用 Arbotix 实现此功能。 Arboti…...

ElasticSearch第十九讲 ES-best fields,most fields策略

multi-field多字段搜索 假设有个网站允许用户搜索博客的内容,以下面两篇博客内容文档为例: PUT /my_index/my_type/1 {"title": "Quick brown rabbits","body": "Brown rabbits are commonly seen." }PUT /my_index/my_type/2 {&…...

Netty详解,5分钟了解,面试不用慌

1. 概述 1.1 Netty 是什么&#xff1f; Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty 是一个异步的、基于事件驱动的网络应用框架&#xff0c;用…...

Logstash学习

一、Logstash基础 1、什么是Logstash logstash是一个数据抽取工具&#xff0c;将数据从一个地方转移到另一个地方。下载地址&#xff1a;https://www.elastic.co/cn/downloads/logstash logstash之所以功能强大和流行&#xff0c;还与其丰富的过滤器插件是分不开的&#xff…...

【流畅的Python学习笔记】2023.4.22

此栏目记录我学习《流畅的Python》一书的学习笔记&#xff0c;这是一个自用笔记&#xff0c;所以写的比较随意 元组 元组其实是对数据的记录&#xff1a;元组中的每个元素都存放了记录中一个字段的数据&#xff0c;外加这个字段的位置。简单试试元组的特性&#xff1a; char…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

五子棋测试用例

一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏&#xff0c;有着深厚的文化底蕴。通过将五子棋制作成网页游戏&#xff0c;可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家&#xff0c;都可以通过网页五子棋感受到东方棋类…...