#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@href: https://leetcode.com/problems/regular-expression-matching/description/
@title: Regular Expression Matching
"""
class Token(object):
def __init__(self, c, m):
self.c = c
self.m = m
def __str__(self):
return str(self.c, self.m)
def mm(self):
return self.m
def eq(self, c):
res = None
if self.c == '.' or self.c == c:
res = True
else:
res = False
return res
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
ls, lp = len(s), len(p)
if (ls + lp) == 0:
return True
p1, lt = [], None
s, p = 'a' + s, 'a' + p # isMatch 不能匹配 'a', 'c*a'，需要写的边界太复杂。不如这样改一下
for i in range(0, lp+1):
if p[i] == '*':
lt.m = True
else:
lt = Token(p[i], False)
p1.append(lt)
p = p1
ls, lp = len(s), len(p)
dp = [[False]*(lp+1) for i in range(0, ls+1)]
dp[0][0] = True
for i in range(1, ls+1):
for j in range(1, lp+1):
if p[j-1].eq(s[i-1]):
dp[i][j] = dp[i-1][j-1] # 普通情况
if p[j-1].mm():
dp[i][j] = dp[i][j] or dp[i-1][j] or dp[i][j-1] # 要考虑一个 x* 能匹配多个或一个都匹配不到的情况
else:
if p[j-1].mm():
dp[i][j] = dp[i][j-1] # 不匹配该 x* 的情况
return dp[ls][lp]
if __name__ == '__main__':
a = Solution()
print a.isMatch('aa', 'a')
print a.isMatch('aa', 'aa')
print a.isMatch('aaa', 'aa')
print a.isMatch('aa', 'a*')
print a.isMatch('aa', '.*')
print a.isMatch('ab', '.*')
print a.isMatch('aab', 'a*b*')
print a.isMatch('a', 'c*a')
dp 题目的边界初始值还是很难考虑的， 如果我不用 s, p = 'a' + s, 'a' + p 来预处理一下。真不知道怎么写初始化值！
转载于:https://www.cnblogs.com/tmortred/p/8038685.html
相关资源：Leetcode_Cpp：leetcode_note-源码
