剑指offer19.正则表达式

这道题我一看就有印象,我室友算法课设抽到这题,他当时有个bug让我帮他看一下,然后我就大概看了一下他的算法,他是用动态规划写的,用了一个二维数组,然后我就试着按照这个思路去写,想了一会还是没有思路,就看题解了:
class Solution {public boolean isMatch(String s, String p) {// .可以代替所有字符,*前面的一个字符可以出现任意次包括0次int m = s.length();int n = p.length();boolean[][] dp = new boolean[m+1][n+1];dp[0][0] = true;for(int i =0; i<=m; i++){for(int j=1;j<=n;j++){if(p.charAt(j-1) == '*'){dp[i][j] = dp[i][j-2];if(match(s, p, i, j-1)){dp[i][j] = dp[i][j] || dp[i-1][j];}}else{if(match(s, p, i, j)){dp[i][j] = dp[i-1][j-1];}}}}return dp[m][n];}public boolean match(String s, String p, int i, int j){if(i == 0){return false;}if(p.charAt(j-1) == '.'){return true;}return s.charAt(i-1) == p.charAt(j-1);}}
dp[i][i]表示s的前i个字符与p的前j个是否匹配,进行状态转移时考虑p的第j个字符:
1,如果第j个字符是一个字母,那么必须在s中匹配一个相同的小写字母。

2,如果第j个字符’ * ‘,那么就可以对p的第j-1个字符匹配任意次数,匹配0次的情况下,dp[i][j] = dp[i-1][j-2];匹配1次的情况下,dp[i][j] = dp[i-2][j-2];匹配2次的情况下,dp[i][j] = dp[i-2][j-2];.......

所以综合两种情况有:

matches()是判断两个字符是否匹配的方法,如果字符相同或者模板中的字符是' . '就返回true否则返回false。
dp[0][0] = true,当两个字符是空字符时返回true,最后返回dp[m][n],m是s的长度,n是p的长度。
相关文章:
剑指offer19.正则表达式
这道题我一看就有印象,我室友算法课设抽到这题,他当时有个bug让我帮他看一下,然后我就大概看了一下他的算法,他是用动态规划写的,用了一个二维数组,然后我就试着按照这个思路去写,想了一会还是没…...
Mac Navicat 16试用脚本
一、无限试用脚本如下 #!/bin/bash #/usr/libexec/PlistBuddy -c "print" ~/Library/Preferences/com.navicat.NavicatPremium.plist /usr/libexec/PlistBuddy -c "Delete :91F6C435D172C8163E0689D3DAD3F3E9" ~/Library/Preferences/com.navicat.Navica…...
什么是 webpack?
Webpack 介绍 什么是 webpack? :::tip 官方描述 webpack 是一个用于现代 JavaScript 应用程序的静态模块打包工具。当 webpack 处理应用程序时,它会在内部从一个或多个入口点构建一个 依赖图(dependency graph),然后将你项目中所需的每一个…...
#B. 费解的开关
题目描述 你玩过“拉灯”游戏吗?2525盏灯排成一个5x55x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应…...
Docker离线安装
Docker离线安装 一、安装步骤 1. 下载 Docker 二进制文件(离线安装包) 下载地址:https://download.docker.com/linux/static/stable/x86_64/ 注:本文使用 /x86_64/docker-18.06.1-ce.tgz,注意对应操作系统类型。 2.…...
React高阶学习(二)
目录 1. 基本概念和语法2. 组件化开发3. 状态管理4. 生命周期钩子5. 条件渲染6. 循环渲染7. 事件处理8. 组件间通信9. 动画效果10. 模块化开发 1. 基本概念和语法 React 是基于 JavaScript 的库,用于构建用户界面。它采用虚拟 DOM 技术,能够高效地渲染页…...
C语言中的字符串输入操作详解
C语言输入字符串详解 目录 介绍使用scanf_s输入字符串scanf_s的限制和问题解决输入空格的方法——使用gets_s函数gets_s函数的注意事项示例代码演示总结 1. 介绍 在C语言中,输入字符串是常见的操作。本篇博客将详细讨论在C语言中输入字符串的方法。我们将使用s…...
C高级 DAY1
1.思维导图 二、 网络配置 更新资源库 在线下载 卸载安装包 离线下载 离线安装包卸载 cat echo head tail 管道符 字体变色 find file grep cut 截取字符 chown ln硬链接 软链接 压缩、解压缩 打包并压缩,解压缩...
centos7 默认路由顺序调整(IPV4_ROUTE_METRIC)
1、问题说明 A服务器有两张网卡,A1对应公网,A2对应私网,公网访问时,访问异常,内网访问服务则显示正常。 问题判断:数据包从公网进来时,路由无需判断,但数据包出去时,有…...
STM32 DMA学习
DMA简称 DMA,Direct Memory Access,即直接存储器访问。DMA传输方式无需CPU直接控制传输,也没有中断处理方式那样保留现场和恢复现场的过程,通过硬件为RAM与I/O设备开辟一条直接传送数据的通路,能使CPU的效率大为提高。…...
32.利用fmincon 解决 最小费用问题(matlab程序)
1.简述 fmincon函数非线性约束下的最优化问题 fmincon函数,既是求最小约束非线性多变量函数 该函数被用于求如下函数的最小值 语法如下: x fmincon(fun,x0,A,b) x fmincon(fun,x0,A,b,Aeq,beq) x fmincon(fun,x0,A,b,Aeq,beq,lb,ub) x fmincon(fun,x0,A,b,Aeq…...
Delphi 开发的QR二维码生成工具,开箱即用
目录 一、基本功能: 二、使用说明: 三、操作演示gif 四、下载链接 在日常的开发中,经常需要将一个链接生成为二维码图片,特别是在进行支付开发的时候,因为我们支付后台获取了支付链接,需要变成二维码扫…...
Springboot使用AOP编程简介
AOP简介 AOP(面向切面编程)是一种编程范式,Spring AOP是基于代理模式的AOP框架,它通过动态代理实现切面的织入,更加轻量级和易于使用。 Joinpoint (连接点):类里面可以被增强的方法即为连接点。例如,想修…...
Android性能优化—卡顿分析与布局优化
一、什么是卡顿?或者说我们怎么感知APP卡顿? 这里面涉及到android UI渲染机制,我们先了解一下android UI是怎么渲染的,android的View到底是如何一步一步显示到屏幕上的? android系统渲染页面流程: 1&…...
【二分+滑动窗口优化DP】CF883 I
Problem - 883I - Codeforces 题意: 思路: 首先,要让最大值最小,很显然要二分 那么就相当于有了一个极差的限制,看能不能分组,每组至少m个元素 那么就是考虑分段DP,直接n^2很容易写 但是n …...
4.netty源码分析
1.pipeline调用handler的源码 //pipeline得到双向链表的头,next到尾部, 2.心跳源码 主要分析IdleStateHandler3个定时任务内部类 //考虑了网络传输慢导致出站慢的情况 //超时重新发送,然后关闭 ReadTimeoutHandler(继承IdleStateHandler 直接关闭连接)和WriteTimeoutHandler(继…...
性能优化点
Arts and Sciences - Computer Science | myUSF 索引3层(高度为3)一般对于数据库地址千万级别的表 大于2000万的数据进行分库分表存储 JVM整体结构及内存模型 JVM调优:主要为减少FULL GC的执行次数或者减少FULL GC执行时间 Spring Boot程序…...
leetcode301. 删除无效的括号(java)
删除无效的括号 leetcode301. 删除无效的括号题目描述暴力搜索 剪枝代码演示 回溯算法 leetcode301. 删除无效的括号 难度 困难 https://leetcode.cn/problems/remove-invalid-parentheses/description/ 题目描述 给你一个由若干括号和字母组成的字符串 s ,删除最小…...
快速制作美容行业预约小程序
随着科技的不断进步,移动互联网的快速发展,小程序成为了很多行业迅速发展的利器。对于美容行业来说,一款美容预约小程序不仅可以方便用户进行预约,还可以提升美容店铺的服务质量和管理效率。下面,我们来介绍一下如何快…...
Golang之路---03 面向对象——结构体
结构体 结构体定义 在之前学过的数据类型中,数组与切片,只能存储同一类型的变量。若要存储多个类型的变量,就需要用到结构体,它是将多个任意类型的变量组合在一起的聚合数据类型。 每个变量都成为该结构体的成员变量。 可以理…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
