# Leetcode Regular Expression Matching

### 题目：Regular Expression Matching

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).

Note:

• `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 `*`.

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```

### 解答：

```class Solution:
def isMatch(self, s, p):
m, n = len(s), len(p)
if n > 0 and p[0] == '*': return False

s, p = s + '#' , p + '#'    # the hashtags mark the end of string/pattern

prev = [False] * (m+1)
current = [False] * (m+1)
prev[-1] = True            # end of pattern matches end of string

for i in range(n-1,-1,-1):
if True not in prev: return False     # terminate early
if p[i] == '*': continue         # ignore * and move to next char in pattern

elif p[i] != '.' and p[i+1] == '*':
current[-1] = prev[-1]
for j in range(m-1,-1,-1):
current[j] =  prev[j] or (p[i] == s[j] and current[j+1])

elif p[i] == '.' and p[i+1] == '*':
current[-1] = prev[-1]
for j in range(m-1,-1,-1):
current[j] = current[j+1] or prev[j]
elif p[i] == '.':
for j in range(m-1,-1,-1):
current[j] = prev[j+1]
else:
for j in range(m-1,-1,-1):
current[j] = prev[j+1] and p[i] == s[j]

prev = current
current = [False] * (m+1)

return prev[0] ```

193 篇文章34 人订阅

0 条评论

## 相关文章

在前面的几篇讨论里我们初步对FP有了些少了解：FP嘛，不就是F[A]吗？也是，FP就是在F[]壳子（context）内对程序的状态进行更改，也就是在F壳子（...

20570

15940

11120

22670

### [C#3] 1-扩展方法

1.从DEMO开始 先看一个扩展方法的例子： 1 class Program 2 { 3 public static void Main(...

224100

### JS魔法堂：再识Number type

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   本来只打算理解JS中0.1 + 0.2 == 0.300000000000000...

23950

23220

### 函数式编程与面向对象编程[1]: Lambda表达式 函数柯里化 高阶函数函数式编程与面向对象编程[1]: Lambda表达式 函数柯里化 高阶函数.md

For example, in Lisp the 'square' function can be expressed as a lambda expressi...

8520

### ST算法

RMQ（Range Minimum/Maximum Query），即区间最值查询。对于长度为n的数列arr，回答若干询问Q(i,j)，返回数列arr中下标在i...

23820

19220