8ffb1cf8cf9192d2383f8025fe143425
Problem 10: Regular Expression Matching

Problem 10: Regular Expression Matching

链接:https://leetcode.com/problems/regular-expression-matching/

难度等级: Hard(困难)

题干

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

注意

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *

s串只包含小写字母,p串只包含小写字母和'.'以及'*'两种特殊字符。

题意

给定s,p两个字符串,返回这两个字符串做正则匹配的结果。

其中s串是原串,p串是匹配串。p串当中除了字符之外,还有两种正则表达式当中的特殊字符。一种是'.',表示可以匹配任意字符。另一种是' * ',表示' * '之前的字符可以出现任意多次(也可以是零次)。

样例

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

分析

这道题初看时并不难,似乎只要一位位匹配,然后返回匹配结果就行了。但是由于存在' * '这种特殊的字符,我们并不知道' * '到底代表了多少个字符。所以按位一位一位匹配来验证是做不到的。

这个问题可以通过暴力枚举的方法解决吗?

好像并不太行,因为我们并不能确定p串当中包含多少个字符' * ',所以没办法枚举对于每一个' * ',它究竟匹配多少长度。

由于存在' * ',还是有点复杂。所以我们先不考虑' * '的情况,假设p串当中除了字母就是'.'。那么会变成什么样?

比如s串是“mississippi”,p串是“mississ.p.”。我们先判断它们的最后一位,发现能匹配,那么再判断倒数第二位,依次往前。如果一直到第0位也能成功匹配,那么说明这两个字符串符合正则表达式的要求,返回true,否则返回false。

```

top Created with Sketch.