10. Regular Expression Matching
Given an input string (s) and a pattern (p), 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).
Note：
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: "." means "zero or more () of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
正则表达式匹配，想偷懒的话，直接调用python的re库
import re
class Solution:
def isMatch(self, s: str, p: str) -> bool:
return re.fullmatch(p, s) != None
比较正规的方法是用动态规划的方法
class Solution:
def isMatch(self, s: str, p: str) -> bool:
ls=len(s)
lp=len(p)
dp = [[True if not j else not ls for j in range(ls+1)] for i in range(lp+1)]
s=' '+s
p=' '+p
for i in range(1, lp+1):
ast = p[i] == '*'#注此处i-1代表第i个
dp[i][0] = ast and dp[i-2][0]
for j in range(1, ls+1):
dp[i][j] = ast and dp[i-2][j] or p[i-ast] in ('.', s[j]) and dp[i-1+ast][j-1]
return dp[lp][ls]
分析一下算法思路
其中递推项dp[i][j]表示p的前i个字符与s中前j个字符组成的表示式是否匹配。dp[0][0]恒为True。
对p和s做1个偏移调整
对于p的前i个和s的前j个字符串
需考虑2种情况
㈠当p[i]='*'时，dp[i][j]为真有两种情况：
(1)当dp[i-2][j]为真时，利用p[i]='*'，可将p[i-1]消去，因此dp[i][j]仍为真，
(2)当dp[i][j-1]为真，且p[i]='*'，则可知s[j-1]一定和p[i-2]或p[i-1]相等
①当s[j-1]==p[i-2]，若s[j]==p[i-1](p[i-1]等于'.'也成立)，则可以令p[i]的'*'为重复1次，正好匹配；
②当s[j-1]==p[i-1]，若s[j]==p[i-1](p[i-1]等于'.'也成立)，则可以令p[i]的'*'为重复2次，正好匹配
㈡当p[i]!='*'时，dp[i][j]为真只有一种情况，dp[i-1][j-1]为真且s[j]==p[i](p[i]等于'.'也成立)。
则可以列出下列递推式
