文档章节

【动态规划】正则表达式匹配

o
 osc_wws45aot
发布于 2019/08/20 02:19
字数 409
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

【题目链接】:

https://www.acwing.com/problem/content/28/

 

【题目解释】

请实现一个函数用来匹配包括'.''*'的正则表达式。

模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。

在本题中,匹配是指字符串的所有字符匹配整个模式。

例如,字符串"aaa"与模式"a.a""ab*ac*a"匹配,但是与"aa.a""ab*a"均不匹配。

样例

输入:

s="aa"
p="a*"

输出:true

【参考】y总的视频讲解。

分3种情况来讨论问题,f[i][j] 以i为结尾的s串是否匹配以j为结尾的p串。

 

具体可以看代码:

 

 1 /*
 2 s="aa"
 3 p="a*"
 4 
 5 f[i][j] 指的是: s[i,...] p[j,...] 相匹配
 6 
 7 1. 当p[i] 是正常的字符 , s[i] == p[j] , f[i][j] = f[i+1][j+1]
 8 2. 当p[i] = '.' ,  f[i][j] = f[i+1][j+1]
 9 3. 当p[i+1] = '*' ,f[i][j] = f[i][j+2] || f[i+1][j]
10 
11 
12 边界问题 : f[n][m] = true;
13 */
14 
15 
16 
17 class Solution {
18 public:
19     string s , p  ;
20     vector< vector<int > > f ;
21     int n, m ;
22     bool isMatch(string _s, string _p) {
23         s = _s , p = _p ;
24         n = s.length() , m = p.length() ;
25         f = vector<vector<int>>( n+2 , vector<int> ( m+2 , -1 ) );
26         return dp(0,0);
27     }
28     bool dp(int x,int y){
29         if( f[x][y] != -1 ) return f[x][y] ;
30         if( y == m )    return (f[x][y] = (x==n));
31         bool First = (x < n && (p[y] == '.' || s[x] == p[y]) ) ; 
32         
33         if( y+1 < m && p[y+1] == '*' ){
34             f[x][y] = dp(x,y+2) || First && dp(x+1,y);
35         }else{
36             f[x][y] =  First && dp(x+1,y+1);
37         }
38         return f[x][y];
39     }
40 };

 

 

 

 

 

 
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
LeetCode 10. 正则表达式匹配 | Python

正则表达式匹配 题目来源:https://leetcode-cn.com/problems/regular-expression-matching 题目 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '' 的正则表达式匹配。 '.......

osc_ym1l2qni
05/03
16
0
LeetCode 10 正则表达式匹配

10 正则表达式匹配 一、题目 给定一个字符串和一个字符模式。实现支持和的正则表达式匹配。 匹配应该覆盖整个字符串,而不是部分字符串。 说明: 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 二...

AiFan
2019/04/28
0
0
LeetCode 10. 正则表达式匹配 | Python

10. 正则表达式匹配 题目来源:https://leetcode-cn.com/problems/regular-expression-matching 题目 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。......

"大梦三千秋
05/02
0
0
Leetcode:NO.44 通配符匹配 动态规划+回溯

题目 给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。 ‘?’ 可以匹配任何单个字符。 ‘*’ 可以匹配任意字符串(包括空字符串)。 两个字符串完全匹配...

泛泛之素
07/05
0
0
Leetcode 1-10题分析总结

1. 两数之和 容易,考察HashMap数据结构 2. 两数相加 容易,链表模拟 3. 最大无重复字串 中等,双指针划窗加HashMap 4. 寻找两个正序数组的中位数 困难,分治法 5. 最长回文字串 中等,中心扩...

wwxy261
06/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

vue input 获取焦点

1、首次加载 autofocus="autofocus" #autofocus 属性规定当页面加载时 input 元素应该自动获得焦点。<input type="text" class="rename_box" v-model="current_edit_text" @input="chang......

横着走的螃蟹
7分钟前
0
0
socket链接(底层)

客户端 #socket.socket表明协议并生成链接实例client #client.connect链接到服务器client #循环输入while true #输入的消息 msg = input #client.send(msg.encode())发送信息只能发送比特流进...

onedotdot
14分钟前
18
0
在线讲解一分快3和值怎么计算的

在线讲解一分快3和值怎么计算的老师:【扣 677~90~572】1.The past is gone and static. Nothing we can do will change it. Thefuture is before us and dynamic. Everything we do will af......

yiren081
14分钟前
8
0
hbase学习

简介 数据存储模型及关系型数据库的区别 一般都是牺牲一致性, 最终达到最终一致性 HBase 概念 区别 基础架构 HBASE 原理和操作 写流程 预写入会写入HLog 里面, 通过HLog 来保证数据不丢失 ...

之渊
15分钟前
15
0
网上彩票为什么会有人带你靠谱吗61861585

老师叩:61861585使用默认的随机源随机排列指定的列表。(打乱list中的数据)sort(List<T> list) 进行排序一个人,身边有多少人,就有多大的世界,有什么样的人,就有什么样的世界。这些人素养...

jiukan49
18分钟前
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部