题目描述
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
# -*- coding:utf-8 -*-
class Solution:
def match(self, s, pattern):
# write code here
dp = [[False for _ in range(len(pattern)+1)] for _ in range(len(s)+1)]
dp[0][0] = True
for i in range(0,len(pattern)-1,2):
if pattern[i+1]=='*': dp[0][i+2]=True
for i in range(1, len(s)+1):
for j in range(1, len(pattern)+1):
# if pattern[j-1] is alphabatic or '.'
if s[i-1]==pattern[j-1] or pattern[j-1]=='.': dp[i][j]=dp[i-1][j-1]
else:
# *before always has sth
if s[i-1]!=pattern[j-2] and pattern[j-2]!='.': dp[i][j]=dp[i][j-2]
else:
dp[i][j]=(dp[i][j-2] or dp[i-1][j-2] or dp[i-1][j])
return dp[len(s)][len(pattern)]
