字符串的自动规划考察匹配的偏多，关键找出匹配的动态转移公式。
5. Longest Palindromic Substring（Medium)
dp[i][j] 代表s[j:i+1] 是否为回文子串
分三种情况为回文子串
如果 s[i] == s[j]，则下面三种情况dp[i][j]=True
(1) i==j 单个字符为回文
(2) i == j+1 相邻两字符相同为回文
(3) dp[i-1][j+1] 即j+1到 i-1 为回文子串则dp[i][j]为回文子串
def longestPalindrome(self, s):
n = len(s)
dp = [[False] * n for _ in range(n)]
left = right = 0
for i in range(n):
for j in range(i+1):
if s[i] == s[j] and (i-j <= 1 or dp[i-1][j+1]): #三种情况包含
dp[i][j] = True
if dp[i][j] and i-j > right - left: #记录最大长度
right = i
left = j
return s[left:right+1]
10. Regular Expression Matching（Hard)
类似题型：44. Wildcard Matching
同样的二位dp，dp[i][j]表示s[:i]与s[:j]匹配。
分一下几种情况讨论：
if p[j] == s[i], 则该位匹配成功 dp[i][j] = dp[i-1][j-1]
同理if p[j] == '.' , dp[i][j] = dp[i-1][j-1]
如果elif p[j] == "", 若p[j] ！= s[i] and p[j] ！= '.' dp[i][j] = dp[i][j-2]
否则，
dp[i][j] = dp[i-1][j] //in this case, a counts as multiple a 匹配多个a
dp[i][j] = dp[i][j-1] // in this case, a* counts as single a 匹配一个a
dp[i][j] = dp[i][j-2] // in this case, a* counts as empty 匹配空
def isMatch(self, s: str, p: str) -> bool:
dp = [ [False] * (len(p)+1) for _ in range(len(s)+1)]
dp[0][0] = True
for i in range(1, len(p)): #空字符只能匹配 以c*a*开始的特殊情况
if p[i] == '*' and dp[0][i-1]:
dp[0][i+1] = True
for i in range(len(s)):
for j in range(len(p)):
if p[j] == s[i] or p[j] == '.':
dp[i+1][j+1] = dp[i][j]
if p[j] == '*':
if p[j-1] != s[i] and p[j-1] != '.':
dp[i+1][j+1] = dp[i+1][j-1]
else:
dp[i+1][j+1] = dp[i][j+1] or dp[i+1][j] or dp[i+1][j-1]
return dp[-1][-1]
72. Edit Distance（Hard)
与上一题也有些类似，不过这次是三种操作替换、删除和添加.
dp[i][j] 代表word1[....i]与word2[....j]替换的最小次数，原理如下
dp[i][j] = min(
dp[i - 1][j - 1] | word1[i - 1] == word2[j - 1], // word1的第i个字符等于word2的第j个字符
dp[i - 1][j - 1] + 1, // 将word1[i - 1]和word2[j - 1]替换为同一个字母
dp[i - 1][j] + 1, // 删去word1[i - 1] 或 在word2[j - 1]的后面添加一个字母
dp[i][j - 1] + 1 // 在word1[i - 1]的后面添加一个字母 或 删去word1[j - 1]
)
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m, n = len(word1) + 1, len(word2) + 1
dp = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
dp[i][0] = i
for j in range(n):
dp[0][j] = j
for i in range(1, m):
for j in range(1, n):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
return dp[-1][-1]
97. Interleaving String（Hard)
dp[i][j] 代表s1[...i] s2[....j]匹配到s3[....i+j-1]
接着就简单了。
def isInterleave(self, s1, s2, s3):
"""
:type s1: str
:type s2: str
:type s3: str
:rtype: bool
"""
len1, len2, len3 = len(s1), len(s2), len(s3)
if len3 != len1 + len2:
return False
dp = [[False] * (len2+1) for _ in range(len1+1)]
for i in range(len1+1):
for j in range(len2+1):
if i == 0 and j == 0:
dp[i][j] = True
elif i == 0:
dp[i][j] = dp[i][j-1] and s2[j-1] == s3[j-1]
elif j == 0:
dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i-1]
else:
dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[j+i-1]) or (dp[i-1][j] and s1[i-1] == s3[i+j-1])
return dp[-1][-1]
115. Distinct Subsequences（Hard)
def numDistinct(self, s: str, t: str) -> int:
#dp[i][j] 为s[...i-1] 与t[....j-1]匹配不同的次数
dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)+1):
dp[i][0] = 1
for i in range(1, len(s)+1):
for j in range(1, len(t)+1):
if s[i-1] != t[j-1]: #不相等只能是匹配到s[i-2]
dp[i][j] = dp[i-1][j]
else: #删除或不删除都可以
dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
return dp[-1][-1]
