题目描述：
难度：Hard
相关话题：字符串、动态规划、回溯算法
给定一个字符串( s ) 和一个字符模式( p )。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个 字符串( s ) ，而不是部分字符串。
说明:
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释:'*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例3:
输入:
s = "ab"
p = ".*"
输出: true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释:'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
思路：
动态规划,dp[i][j]代表到索引[0,i]的p是否能被索引[0,j]的s匹配。
如果p[i]===s[j] || p[i]==='.'，说明它们匹配，dp[i][j]=dp[i-1][j-1]。
如果不匹配，但是p[i]==='*'，
- 如果
p的前一个能和当前s匹配并且dp[i][j-1]===true，说明*可以延长上一个的p来匹配当前的s； - 如果上面条件不符合，但是
dp[i-2][j]===true，也就是说前2个的p能和当前s匹配，那么*可以作为数量0,相当与忽略前一个p。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let pLen=p.length,sLen=s.length
let dp=Array(pLen+1).fill().map(()=>Array(sLen+1).fill(false))
for(let i=0;i<pLen+1;i++){
for(let j=0;j<sLen+1;j++){
if(i===0 && j===0){
dp[i][j]=true
}else if(p[i-1]==="*" && j===0){
dp[i][j]=dp[i-2][j]
}
}
}
for(let i=1;i<pLen+1;i++){
for(let j=1;j<sLen+1;j++){
let r=i-1,c=j-1
if(p[r]===s[c] || p[r]==='.'){
dp[i][j]=dp[i-1][j-1]
}else if(p[r]==="*"){
if(((p[r-1]===s[c] || p[r-1]===".") && dp[i][j-1]) || dp[i-2][j])
dp[i][j]=true
}
}
}
return dp[pLen][sLen]
};
扩展阅读：