Regular Expression Matching
题目描述
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
解题方法
backtracking + dfs
这道题目最直观的想法就是，应该根据p的情况不断地去试，比较难处理的地方就是有.和*的地方，而这种不断去试的题目
又让我想到了permutation和subset这几题，也就是backtracking + dfs的方法。而且这个思路我们可以去往下想，根据.和*来
进行分情况讨论。
并且我们可以注意到，如果这其中的小问题之间是有联系的，如果之前的部分已经match, 那么我们可以直接recursive call the function on 剩下的string和pattern. 所以这是一个很自然的recursive的方法。
我们可以对p的前两位进行分析，因为只要分析这两位中的.和*情况，就可以进行下一个recursive call了。
首先是len(p) == 0的情况先考虑，这时候如果s也为empty string才match
len(p) == 1 or p[1] != "*"
因为p的第一位不能是*，所以我们只需要考虑p[1]是否为*， 因为只有为*时，才会影响到后面的match, 否则就只需要
单独考虑这一位就可以。
p只剩下一位，那么只需要判断s和这一位的关系就可以了p[1] != "*"， 那么说明p[0]不会match后面的char, 所以可以单独考虑和第一位的关系了p[1] == "*"
这时候前两位就会对后面的match产生影响了，*代表可以match zero or more characters，而到底是多少我们不知道，
所以需要一个一个地去试，这里就可以写一个loop，最短match 0位，最长match 整个string来试。
超出了leetcode的time limit
DP
这里的子问题直接是有联系的，并且只要求能与不能，我们又可以往DP的方向想。
state
dp[i][j] 表示s[:i+1]可以由p[j+1] match
init status
就是s长度为0和p长度为0的时候
function
这里的function比较复杂，也需要分情况讨论，dp[i][j]肯定是由之前的状态得来
p[j-1] != "." and p[j-1] == "*"
之前一个不是特殊字符，那么只需要check当前这一位就可以了。
if dp[i-1][j-1] and s[i-1] == p[j-1]:
dp[i][j] = True
p[j-1] == "."
当前这一位可以match任何字符，并且必须match一位，那么dp[i][j] = dp[i-1][j-1]
p[j-1] == "*"
这时候又有了很多种情况，p[j-2]可以match zero or more characters, 而match次数>=2的时候可以再退回到0或1的情况
if dp[i][j-2] == True, 说明match 0的情况可以成功，就可以将dp[i][j]设为Trueif dp[i][j-1] == True, 说明match 1的情况可以成功- match 2次以上的情况，可以退回到
dp[i-1][j]， 最终可以退到0次或1次if dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == "."): dp[i][j] = True- 这个能想到很重要，否则match 2次以上很难处理。可以试着找找前后的关系找灵感
注意点
dp[i][j]代表的是前i个，前j个字符，而不是Index, 在初始化dp的时候要比长度多一位
two pointer方法
Solution
backtracking + dfs
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(p) == 0:
return len(s) == 0
if len(p) == 1 or p[1] != "*":
if len(s) == 0 or ( s[0] != p[0] and p[0] != "."):
return False
return self.isMatch(s[1:], p[1:])
else:
i = - 1 # 因为要试验match 0位，所以这里从-1开始，考虑match 0 位的情况
# i < 0 -- match 0
# p[0] == "." or p[0] == s[i]都表示可以match当前位
while i < len(s) and ( i < 0 or p[0] == "." or p[0] == s[i]):
if self.isMatch(s[i+1:], p[2:]):
return True
i += 1
return False
DP
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(p) == 0:
return len(s) == 0
lengthS = len(s)
lengthP = len(p)
dp = [[False for i in range(lengthP + 1)] for j in range(lengthS + 1)]
dp[0][0] = True
# init state, match no characters
# last char in pattern has to be "*", which match 0 characters
for i in range(2, lengthP + 1):
if p[i-1] == "*":
dp[0][i] = dp[0][i-2]
for i in range(1, lengthS + 1):
for j in range(1, lengthP + 1):
if p[j-1] != "." and p[j-1] != "*":
if dp[i-1][j-1] and s[i-1] == p[j-1]:
dp[i][j] = True
elif p[j-1] == ".":
dp[i][j] = dp[i-1][j-1]
elif j > 1: # "*" can't be first char
if dp[i][j-2]:
# match 0
dp[i][j] = True
elif dp[i][j-1]:
# match 1
dp[i][j] = True
elif dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'):
dp[i][j] = True
return dp[lengthS][lengthP]