题目来源：
https://leetcode.com/problems/regular-expression-matching/
题意分析：
这道题目定义了两个正则表达式规则。’.’代表任意字符，’*’代表前一个字符出现任意次。输入两个字符串s，p。如果s可以被p完全匹配则返回True，否则返回False。比如’.*’可以匹配任意字符串。
题目思路：
这道题目如果直接import 正则表达式肯定是不行的，因为题目只定义了2个特殊字符，而正则表达式包括很多特殊字符，所以直接import正则表达式肯定是不行的。
从第一个字符开始搜索，对以下情况进行讨论：
①如果（s[0] == p[0]or p[0] == ‘.’）且p的第二个字符不是’*’，那么如果两个字符同时去掉第一个字符，结果不变。
②如果p[0] == ‘.’且p[1] == ‘*’那么如果存在s[i:],i >= 0被p[2:]完全匹配，则s可以被p完全匹配（s[i:]代表s字符除掉0到i下标的字符）。
③如果p[0] != ‘.’且p[1] == ‘*’，那么如果s[0] != p[0]那么如果s可以被p[2:]匹配，则s可以被p完全匹配。
④如果s[0] == p[0]那么如果存在s[i：]（i >= 0 且 s[j] == p[0] 0<= j <i）被p[2:]完全匹配，那么s可以被p完全匹配。
经过上面的分析，这道题目可以用动态规划来做。用b[i][j]来代表由s除掉0到i下标的字符能否被由p除掉0到j下标的字符完全匹配，也就是s[i:]能否被p[j:]完全匹配。根据上一段的分析可以得到：
if p[j + 1] != ‘*’
if s[i] == p[j] or p[j] == ‘.’ then b[i][j] = b[i + 1][j + 1]
fi
else
if p[j] == ‘.’ then
if exist k (i<=k) b[k][j + 2] = true then b[i][j] = true
else b[i][j] = false
fi
else
if exist k(i <= k)b[k][j + 2] = true and all l (0 <= l <k) s[l] = p[0] then b[i][j] =true
else b[i][j] = false
fi
fi
return b[0][0]
PS：由于python的二维数组初始化比较麻烦，或者是因为我对python的不熟，我选择用dictionary来处理，b[i,j]代替b[i][j].
代码（python）：
class Solution(object):
def isMatch(self,s, p):
size1 = len(s)
size2 = len(p)
b = {}
s1 = 0
while s1 <= size1:
s2 = 0
while s2 <= size2:
b[s1,s2] = False
s2 += 1
s1 += 1
b[size1,size2] = True
j = size2 - 1
while j >= 0:
if p[j] == '*':
b[size1,j] = False
j -= 1
b[size1,j] = True
j -= 1
else:
break
j = size2 - 1
while j >= 0:
if p[j] == '.':
i = size1 - 1
while i >= 0:
b[i,j] = b[i + 1,j + 1]
i -= 1
elif p[j] != '*':
i = size1 - 1
while i >= 0:
if p[j] == s[i]:
b[i,j] = b[i + 1,j + 1]
else:
b[i,j] = False
i -= 1
else:
i = size1 - 1
if p[j - 1] == '.':
while i >= 0:
k = i
while k <= size1:
if b[k,j + 1]:
b[i,j - 1] =True
break
k += 1
i -= 1
else:
while i >= 0:
k = i
while k <= size1:
if b[k,j + 1]:
b[i,j - 1] = True
break
if k == size1:
break
if p[j - 1] != s[k]:
break
k +=1
i -= 1
j -= 1
j -= 1
return b[0,0]
转载请注明出处：http://www.cnblogs.com/chruny/p/4807234.html