题目：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。*
'.' 匹配任意单个字符
'' 匹配零个或多个前面的那一个元素*
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
输入：s = "mississippi" p = "mis*is*p*."
输出：false
自行解答
总共可以采用2种办法解决
1：递归解决
递归解决首先解决递归的子问题划分，首先可以根据题目的说法，本题 的难点其实就在p字符中的 (字符 +*) 此种组合对应到s字符中的实际情况，所以首先按照 P字符的(字符 +*)来划分2中大情况：
1.1： (字符 + *)组合
此种组合其实解决4种情况就可以得到问题答案，即
-
0个字符情况：
s:bb
p:a*bb
-
1个字符情况
s:abb
p:a*bb
-
多个字符情况
s:aaaaaaabb
p:a*bb
-
.*组合情况
s:cbb
p:.*bb
这些情况互斥，也就是说发生0个字符的 就不会发生1个字符的，发生一个字符的，就不会发生多个字符的，因此在这种组合下，当前状态的结果应该是
bool result = false;
result = (0个字符)||(1个字符)||(多个字符)||(.*组合情况)；
0个字符的情况下，result = isMatch(s,p.substr(2))
1个字符，多个字符，以及.*组合情况如果穷举，1个的字符或能穷举，但是多个的无法穷举，但是换个角度想，多个的其实可以用另外2个状态的或集来表示，如：s:aaaaaabb p:a*bb s是否匹配p，其实问题等价于
bool result1 =(aaaaabb|| aaaabb ||aaabb ||aabb ||aabb || abb ) 是否匹配p
bool result2 = bb 是否匹配p.sunstr(2)
bool result = result1 || result2
这样就把这个p以(字符 + *)组合的情况 下的2中小情况分析完毕了
1.2：其他组合
此种状态s想要匹配p,只有一种情况：
bool result = !s.empty() &&
((p[0] == s[0]) || p[0]== '.') &&
isMatch_try(s.substr(1),p.substr(1));
也就是s 不为空，且（p和s的首字符相等 或者 p的首字符为'.' ）且s去掉首字符的剩余字符和p去掉首字符的剩余字符也能匹配上
按照此种逻辑即可使用递归实现
代码实现：
class Solution {
public:
bool isMatch(string s,string p){
// cout << "=========begin=======" <<endl;
// cout << "s:" <<s<<endl;
// cout << "p:" <<p<<endl;
if(p.empty()){
// cout << "=========empty=======" <<endl;
return s.empty();
}
bool result = false;
if(p[1] == '*'){
if(!s.empty() && (s[0] == p[0] || p[0] == '.')){
//匹配p中带*时，s首字符为 1个 多个 .*三种情况下是否s能匹配上p
result = isMatch(s.substr(1),p) ||isMatch(s,p.substr(2));
} else{
//匹配p中带*时 匹配0个时，s能够匹配上p的场景
result = isMatch(s,p.substr(2));
}
} else {
result = !s.empty()&& ((p[0] == s[0]) || p[0]== '.') && isMatch(s.substr(1),p.substr(1));
}
// cout << "=========end=======" <<endl;
return result;
}
};
2：动态规划
其实上面的递归的场景明白之后，很容易改出来经典动态规划的场景，改出来动态规划的算法主要明白了几点即可实现：
- dp[i][j]:含义是s的前i个字符能否被p的前j个字符匹配
- dp表的base case 应该是dp[0][0] =true,即 0个字符的s和0个字符的p一定是匹配的
- dp[][]中 的值的填写方式其实和上面的的递归是一样的
- 题目的解就是 dp[s.length][p.length]的值
明白上诉三点即可写出动态规划的代码实现，下面的代码实现为了防止越界可采用在s和p 字符前面增加空字符，防止越界
代码如下：(代码写完未经整理，可整理成更加简洁版本)
bool isMatch(string s,string p){
s = " "+s;
p = " " +p;
int sLength = s.length();
int pLength = p.length();
vector<vector<bool>> dp;
for(int i = 0;i<sLength;i++){
vector<bool> v;
v.resize(pLength);
dp.push_back(v);
}
dp[0][0] = true;
//初始化第一行
for(int i = 1;i<pLength;i++){
if(p[i] == '*'){
//不会出现
dp[0][i] = dp[0][i-2];
} else{
dp[0][i] = false;
}
}
//初始化第一列
for(int i= 1;i<sLength;i++){
dp[i][0] = false;
}
cout<<"行列初始化完毕"<<endl;
for(int si = 1;si<sLength;si++){
for(int pi = 1;pi<pLength;pi++){
if(p[pi] != '*'){
if(s[si] == p[pi] || p[pi] == '.' ){
dp[si][pi] = dp[si-1][pi-1] ;
} else{
//本行可不要，因为初始化均已经初始化成false了
dp[si][pi] = false;
}
} else{
//情况1：*前面的字符只有一个
if(p[pi-1] == s[si] ||p[pi-1] == '.' ){
//* 0次， 多次
dp[si][pi] = dp[si][pi-2] || dp[si-1][pi];
} else {
dp[si][pi]= dp[si][pi-2] ;
}
}
}
}
return dp[sLength-1][pLength-1];
}
3：问题相关思考
1：如何能考虑到是动态规划？
动态规划的题目练习的多了，再见到一定的题目就会连就对动态规划的敏感度，进一步解决这些问题
2：如何能想到递归解决问题？
个人认为递归问题明显的一个特征就是新问题和子问题其实是不同参数的同一问题，在尝试用递归解决问题时需要将递归的参数以及问题求解的划分思考清楚即可采用递归解决
3：递归和动态规划的关系
在采用递归解决问题时，会把当前问题的转化成子问题进行递归，子问题的状态的并集 （&&）和 与集（||）的结果就是当前问题的答案，这个时候 子问题其实代表的不就是动态规划表中dp中的某一个位置的值么，因此，递归算法写完，一定能改写成动态规划的写法，而且动态规划的转移方程就是递归函数中子函数的并集 和与集的关系，做一个转换就行，其实是一码事
4：如何做到遇到问题很快想到动态规划的转移方程
首先我认为遇到问题先按照递归的思路分析，这样是最贴合人的思维以及解决问题的流程的，当然在这个步骤很熟悉之后，你想到了这个递归解决办法中的思路划分和子问题解决方案就自然能直接当做动态规划的逻辑写code
5：动态规划和递归的复杂度
动态规划：
时间复杂度：O(s.length * p.length),就是填写dp表的时间
空间复杂度：O(s.length * p.length),就是dp表的大小，用来表示每一个过程状态的空间是额外申请的
递归：
时间复杂度：O(2N)
空间复杂度：O(2N)
时空复杂度全是 是2的n次方，为指数级别，因此能想通递归算法，就一定改成经典动态规划，时空复杂度提升一个级别
网友评论