Error message here!

Hide Error message here!

Error message here!

Hide Error message here!

Error message here!

Close

## LeetCode10 Hard，带你实现字符串的正则匹配

TechFlow2019 2020-01-20 08:36:00 阅读数:56 评论数:0 点赞数:0 收藏数:0

Regular Expression Matching

Hard

## Description

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

### 题解

``````def match(s, p):
n = len(s)
for i in range(n):
if s[i] == p[i] or p[i] == '.':
continue
return False
return True``````

``````def match(s, p, i, j):
# 当前位置是否匹配
flag = s[i] == p[j] or p[j] == '.'
# 判断p[j+1]是否是*，如果是那么说明p[j]可以跳过匹配
if j+1 < len(p) and p[j+1] == '*':
# 两种情况，一种是跳过p[j]，另一种是p[j]继续匹配
return match(s, p, i, j+2) or flag and match(s, p, i+1, j)
else:
# 如果没有*，只有一种可能
return flag and match(s, p, i+1, j+1)``````

``````memory = {}
def match(s, p, i, j):
if (i, j) in memory:
return memory[(i, j)]
# 当前位置是否匹配
flag = s[i] == p[j] or p[j] == '.'
# 判断p[j+1]是否是*，如果是那么说明p[j]可以跳过匹配
if j+1 < len(p) and p[j+1] == '*':
# 两种情况，一种是跳过p[j]，另一种是p[j]继续匹配
ret = match(s, p, i, j+2) or flag and match(s, p, i+1, j)
else:
# 如果没有*，只有一种可能
ret = flag and match(s, p, i+1, j+1)
memory[(i, j)] = ret
return ret``````

s = 'aaaaa'

p = '.*'

``````def is_match(s, p):
# 为了防止超界，我们从下标1开始
s = '\$' + s
p = '\$' + p
n, m = len(s), len(p)
dp = [[False for _ in range(m)] for _ in range(n)]
dp[0][0] = True
# 需要考虑s空串匹配的情况
for i in range(n):
for j in range(1, m):
# 标记当前位置是否匹配，主要考虑s为空串的情况
match = True if i > 0 and (s[i] == p[j] or p[j] == '.') else False
# 判断j位置是否为'*'
if j > 1 and p[j] == '*':
# 如果是，只有两种转移的情况，第一种表示略过前一个字符，第二种表示重复匹配
dp[i][j] = dp[i][j-2] or ((s[i] == p[j-1] or p[j-1] == '.') and dp[i-1][j])
else:
# 如果不是，只有一种转移的可能
dp[i][j] = dp[i-1][j-1] and match
return dp[n-1][m-1]``````

https://www.cnblogs.com/techflow/p/12216544.html