【打卡】牛客网：BM76 正则表达式匹配
模板的：
关键思想是：
当pattern遇到*时，需要考虑两种情况：
- str的当前字符和pattern的*前的字符相同，例如str=“ab”，pattern=“abb*”，“b”和“b*”相同，有两种情况可以选择：
- pattern的“b*”发挥作用，即去掉str的当前字符，即考虑“a”和“abb*”。 //易错，不是考虑“a”和“ab”
- pattern的“b*”不发挥作用，即不去掉str的当前字符，即考虑“ab”和“ab”。
- str的当前字符和pattern的*前的字符不同，只有一种情况：
- “ac”和“ab*”的“c”和“b*”不同，“b*”不发挥作用，即不去掉str的当前字符，即考虑“ac”和“a”。
没有遇到*时，正常递归：
- 二者的当前字符相同，考虑二者的之前的，即dp[i][j]=dp[i-1][j-1];
- 二者的当前字符不相同，直接str不符合pattern，dp[i][j]=false;
此外，pattern还有“.”的匹配方式。“.”必须考虑一个字符，所以与判断字符相同的过程一样，即在上述过程中判断条件中“相同”改成“相同或匹配”即可。
初始化问题：
- pattern为空字符串，全部false
- str为空字符串，只有当pattern是【随意一个字符+*】，或者是任意个【随意一个字符+*】的组合时，dp为true。程序中的写法比较巧妙。
我的是dp[n2][n1]。
我习惯把pattern放在列（n2的for循环放在外面），str放在行(n1的for循环放在里面)。
然后对于每一个pattern元素，遍历所有str元素。
模板的是dp[n1][n2]，对于每一个str元素，遍历所有pattern元素。结果都一样。
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param str string字符串 * @param pattern string字符串 * @return bool布尔型*/bool match(string str, string pattern) {// write code hereint n1 = str.length();int n2 = pattern.length();vector<vector<bool>> dp(n2+1,vector<bool>(n1+1,false));dp[0][0] = true;for(int j = 1; j <= n2; j++)if(pattern[j-1] == '*')dp[j][0] = dp[j-2][0];for(int j = 1; j <= n2; j++)for(int i = 1; i <= n1; i++){if(pattern[j-1] == '*')if(pattern[j-2] == str[i-1] || pattern[j-2] == '.')dp[j][i] = dp[j][i-1] || dp[j-2][i]; //满足其一即可elsedp[j][i] = dp[j-2][i];elseif(pattern[j-1] == str[i-1] || pattern[j-1] == '.')dp[j][i] = dp[j-1][i-1];}return dp[n2][n1];}
};