面试题19. 正则表达式匹配
2020-03-11 本文已影响0人
人一己千
题目
请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法
需要分情况做，重点如下：
- 需要备忘录，不然会有很多重复计算；
- 递归结束的条件是字符串到头了，此时看模式的情况返回；
- 对于后面是否带*分情况讨论；
- 如果后面不带*， 则按照普通匹配规则；
- 如果后面带*则分字符串是否到头；
- 字符串到头则对模式进行下一步判断（后面可能还是a*这种）
- 字符串还没到头则进行匹配；
- 能匹配又分为三种情况：a恰好是最后一个a，a对应于空，a*是中间的a。
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
len_s = len(s)
len_p = len(p)
p_list = []
i = 0
while i < len_p:
if i + 1 < len_p and p[i + 1] == '*':
p_list.append(p[i] + p[i + 1])
i += 2
else:
p_list.append(p[i])
i += 1
# print(p_list)
len_p = len(p_list)
mem = {} # 备忘录 用来存
def get_res(i, j):
# i指向字符串 j指向模式
if (i, j) in mem:
# 把已经计算过的子问题保存下来
return mem[(i, j)]
if j == len_p: # 如果模式已经全部匹配
if i == len_s: # 如果字符串也都已经全部匹配
res = True
else: # 字符串没有完全匹配
res = False
else:
if len(p_list[j]) == 1: # 普通字符或者'.'
if i < len_s and (p_list[j] == '.' or s[i] == p_list[j]):
res = get_res(i + 1, j + 1)
else:
res = False
else: # 包括 *
if i < len_s:
if p_list[j][0] == '.' or p_list[j][0] == s[i]:
# 三种情况 a*匹配最后一个a a*匹配空 a*匹配中间的a
res = get_res(i + 1, j + 1) or get_res(i + 1, j) or get_res(i, j + 1)
else:
res = get_res(i, j + 1)
else:
# 这是干啥？
# 字符串已经完了，但是模式还有a*这样的存在结尾可以匹配0次
res = get_res(i, j + 1)
mem[(i, j)] = res
return res
return get_res(0, 0)
# 想用递归求解，又不想重复计算子问题，备忘录方法就巧妙的建立了备忘录，记录每个子问题的解，求解问题过程中先查表，如果该问题已经有答案，则可以直接拿来用，无需重新求解。
总结
要考虑的情况很多，很容易出错啊。
