发大米求问一道coding 题目 regular expression matching

原来翻面经时记得 regular expressio

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

一下，必发大米报答～～～

有两种问法：
这种
https://leetcode.com/problems/wildcard-matching/description/

和这种
https://leetcode.com/problems/regular-expression-matching/description/

主要都是在时间空间上卡你，然后想不同的算法

abcdldzy 发表于 2018-6-4 09:32
有两种问法：
这种
https://leetcode.com/problems/wildcard-matching/description/

谢谢回复

我想问下regular expression 能怎样follow up

记得在地里看到的是在pattern string 前面加 *.  但是死活想不起来具体怎么问的了

几种变形：
1. +*.
2. s是否有字串和p match
3. s 是否 contain p

2 3解法一样

变形可以是s中是否包含任意的substring能match p，可以让p = .*p.* 然后用原算法解

huaye 发表于 2018-6-4 10:26
谢谢回复

我想问下regular expression 能怎样follow up

说实话，这道题要是你当场能够给面试官讲明白，dp和递归的算法都讲清楚，能流畅的实现其中指定的一种，基本这轮你就稳了。这道题要把思路讲明白还是很难的。

你这么纠结followup 无非就是时间空间上卡你，要是能理解dp和递归的各种算法，把leetcode里面的讨论版的解法都过一遍，这题再怎么followup也没问题。

EricYang 发表于 2018-6-4 14:49
几种变形：
1. +*.
2. s是否有字串和p match

多谢回复 已发大米


2,3明白  只是想问下大神说的 第一种  +*. 是什么意思  ？

必再发大米回报～～

.* + p + .*

huaye 发表于 2018-6-5 12:25
多谢回复 已发大米

1.
. 和 *是原题里的， +表示 [1, +00) match