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

深圳网站定制公司中央刚刚宣布大消息

深圳网站定制公司,中央刚刚宣布大消息,邯郸市出租房屋信息网,vi设计公司成都给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。 题解 字符串匹配多…

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

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。
在这里插入图片描述
在这里插入图片描述

题解

字符串匹配多用动态规划法,如72题

一、dp[i][j]:表示 s 的前 i-1个字符和 p 的前 j-1个字符能否匹配

记 s 的长度为 m,p的长度为 n 。为便于状态更新,减少对边界的判断,初始二维 dp 数组维度为 (m+1)×(n+1) ,其中第一行和第一列的状态分别表示字符串 s 和 p 为空时的情况
需要特别注意的是,由于 dp 数组维度为 (m+1)×(n+1),在具体代码实现时,s[i−1] 和 p[j−1] 才是分别表示 s 和 p 中的第 i 和第 j 个字符

二、状态转移:

1.p[j]==s[i](p[j]和s[i]是同一个小写字母/p[j]=‘.’

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

2.p[j]= ‘*’:

1)p[j]匹配0次p[j-1],即丢弃p[j]和p[j-1]
dp[i][j]=dp[i][j-2]
2)p[j]匹配多次p[j-1],即p[j]和p[j-1]匹配了n次,对应s[i-n+1…i],此时需要s[i-n+1]=…=s[i]=p[j-1]||p[j-1]=‘.’
此处转载自flix
在这里插入图片描述
dp[i][j]=dp[i-1][j]

三、初始化

  1. dp[0][0]=True
  2. dp[0][j]=false,j!=’ * ‘,则有 dp[0][j]=dp[0][j−2]
    当 p[j]!=’‘时,s[0,…,j] 无法与空字符匹配,因此有 dp[0][j]=False;而当 p[j]=’'时,则有 dp[0][j]=dp[0][j−2]。
    以 p= “cab” 为例,dp[0][∗]=[True,False,True,False,True,False]。
class Solution {public boolean isMatch(String s, String p) {int m=s.length(),n=p.length();boolean[][] dp =new boolean[m+1][n+1];dp[0][0]=true;for(int i=2;i<n+1;i++){dp[0][i] = dp[0][i - 2] && p.charAt(i - 1) == '*';}//注意遍历从1开始for(int i=1;i<m+1;i++){for(int j=1;j<n+1;j++){//这块这么写是因为字符串和dp的下标差1,为了避免下文写错了char sc = s.charAt(i - 1);char pc = p.charAt(j - 1);if(sc==pc||pc=='.') dp[i][j]=dp[i-1][j-1];else if(pc=='*'){if(dp[i][j-2]) dp[i][j]=true;//s[i]=p[j-1],但是要转化成char才能用“==”比较else if(sc==p.charAt(j-2)|| p.charAt(j - 2) == '.') dp[i][j]=dp[i-1][j];}}}return dp[m][n];}
}
http://www.ds6.com.cn/news/16306.html

相关文章:

  • 网站设计书籍推广一手渠道
  • 安卓从网站获取视频怎么做免费网络营销平台
  • 查网站怎么做的企业如何做网站
  • 如何访问win7下做的网站杭州seo网站推广
  • 爱淘宝淘宝网首页sem和seo是什么职业岗位
  • 大型门户网站建设一般多少钱产品推广方法
  • 网络会议网站自然排名怎么优化
  • 网站制作简单协议如何找推广平台
  • 新疆建设网首页seo网站优化方案书
  • 网站建设与建设百度指数预测
  • 江苏连云港做网站google广告
  • 律师网站建设推荐360优化大师下载
  • 凡科网站做商城独立站推广
  • 做php网站需要什么软件廊坊关键词快速排名
  • 做网站用什么语言简单广州网站建设技术外包
  • 汽车网站首页模板代码磁力链bt磁力天堂
  • pc端网站生成wap版网络软文是什么
  • 网页设计与制作基础教程答案搜索引擎优化不包括
  • 韶关做网站的商城系统开发
  • 招标采购网seo优化几个关键词
  • php企业网站开发框架chrome浏览器下载安卓手机
  • 临颖网站建设谷歌seo关键词优化
  • 做网站的公司上海百度数据网站
  • 建设企业网站流程下载浏览器
  • 海外红酒网站建设电商网站建设
  • 上海网站建设选缘魁 -企查app推广方案
  • 网站建设后的优势口碑营销是什么
  • 网站制作 那种语言好seo关键词优化排名外包
  • 为某网站做网站推广策划方案永久不收费免费的软件
  • 做网站市场报价推广如何做网上引流