10. Regular Expression Matching
dp问题是先找到状态，这一步我找出来了，然后要初始化，我没考虑到下面提到的corner case，然后要写出递推公式，我写出了 p[i] != "*"的情况，然后就不会了。。。研究了一个答案，虽然明白了，但是感觉如果再换一种方式来问，我还是不太能答出来这个问题。也没什么其它办法，估计只能多写两遍，增加对这种题型的感觉和熟练度。
class Solution(object):
def isMatch(self, s, p):
# The DP table and the string s and p use the same indexes i and j, but
# table[i][j] means the match status between p[:i] and s[:j], i.e.
# table[0][0] means the match status of two empty strings, and
# table[1][1] means the match status of p[0] and s[0]. Therefore, when
# refering to the i-th and the j-th characters of p and s for updating
# table[i][j], we use p[i - 1] and s[j - 1].
# Initialize the table with False. The first row is satisfied.
table = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]
# Update the corner case of matching two empty strings.
table[0][0] = True
# Update the corner case of when s is an empty string but p is not.
# Since each '*' can eliminate the charter before it, the table is
# vertically updated by the one before previous. [test_symbol_0]
# 也就是说对于某一个i也就是p[:i]匹配与空串""等于当p[i-1]是为*，p[:i-2]匹配与空串
# 例子 p = "a*b*" p[:4] 匹配与""就等于 p[3] == "*" and p[:2]匹配与空串结果为True
for i in range(2, len(p) + 1):
table[i][0] = table[i - 2][0] and p[i - 1] == '*'
for i in range(1, len(p) + 1):
for j in range(1, len(s) + 1):
if p[i - 1] != "*":
# Update the table by referring the diagonal element.
# 这个好理解，如果当前p值不为*，那么当前的值就等于之前的值and一些当前条件
table[i][j] = table[i - 1][j - 1] and (p[i - 1] == s[j - 1] or p[i - 1] == '.')
else:
# 当此时的字符为*时候，则分为两种情况
# Eliminations (referring to the vertical element)
# Either refer to the one before previous or the previous.
# I.e. * eliminate the previous or count the previous.
# [test_symbol_1]
# 第一种情况是*代表之前的0个字符，或者代表之前的1个字符
# 也就是看看当前的s[:j]是否匹配与 p[:i-1]或者p[:i-2]
table[i][j] = table[i - 2][j] or table[i - 1][j]
# Propagations (referring to the horizontal element)
# If p's previous one is equal to the current s, with
# helps of *, the status can be propagated from the left.
# [test_symbol_2]
# 第二种情况*是扩充了当前的字符
# 也就是说如果s[j-1]也就是当前考虑的字符和p[i-2]也就是*之前的字符相同
# 或者p[i-2]也就是*之前的字符为"."那么可以用当前的匹配 or p[:i] 和 s[:j-1]的匹配
# 例如 p = "ab*" s = "abbbb"
# p[:3] 和 s[:4] 也就是abbb匹配时，因为p[2] = "*" p[1] == s[3]
# 所以 p[:3]和s[:4]的匹配就相当于 or 上 p[:3]和s[:3]的匹配，因为后一位可以由*扩展而来
if p[i - 2] == s[j - 1] or p[i - 2] == '.':
table[i][j] |= table[i][j - 1]
return table[-1][-1]
