Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023562
  • 博文数量: 136
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1800
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(136)

文章存档

2020年(34)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2020-07-13 11:51:25

leetcode第10题,之前提交做过,今天再看到有点乱,写下来记录下;
题目:正则匹配,不过pattern串中只有小写字母,和'.'外加'*'。
其实这道题目如果没有'*'直接一路匹配过去就好了,不用想太多;但是题目中有这个,就得想办法解决了。'*'在正则中表示匹配0个或多个前一个字符,这样的话,如果当前是'*'就得知道前一个字符,这就引导我们去做从后向前的字符串匹配了,具体代码如下:

点击(此处)折叠或打开

  1. bool isMatch(string s, string p){
  2.     int s_len=s.length(), p_len=p.length();
  3.     // dp[i][j] 表示s[i:], p[j:]能否完全匹配
  4.     vector<vector<bool> > dp(s_len+1, vector<bool>(p_len+1, false));
  5.     dp[s_len][p_len]=true;// 空匹配为真
  6.     // pattern 串有可能匹配空,所以
  7.     for(int i=s_len; i>=0; i--){
  8.         for(int j=p_len-1; j>=0; j--){
  9.             // 先判断当前是否能够匹配
  10.             bool is_match = i<s_len&&(s[i]==p[j]||p[j]=='.');
  11.             if(j+1<p_len && p[j+1]=='*'){
  12.                 // 匹配0个或者多个(多个的时候用到了“后向迭代思路”)
  13.                 dp[i][j]=dp[i][j+2]||(is_match && dp[i+1][j]);
  14.             }else{
  15.                 dp[i][j]=is_match && dp[i+1][j+1];
  16.             }
  17.         }
  18.     }
  19.     return dp[0][0];
  20. }

阅读(36) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~