面试题19/leetcode10（正则表达式匹配|面试题19/leetcode10：正则表达式匹配 C++）面试题19

题目：请实现一个函数用来匹配包含 .和* 的正则表达式。模式中的字符.表示任意一个字符，而 *表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与模式"aa.a"及"ab*a"均不匹配。

分析：这道题的核心其实在于分析'*', 对于'.'来说，它和任意字符都匹配，可把其当做普通字符。对于'*'的分析，我们要进行分情况讨论，当所有的情况都搞清楚了以后，就可以写代码了。

当Patttern第二个字符不是*时，情况简单：
如果字符串的第一个字符和模式中的第一个字符匹配，那么在字符串和模式上都向后移动一个字符，然后匹配剩余字符串和模式。
如果字符串的第一个字符和模式中的第一个字符不匹配，那么直接返回false。

在每轮匹配中，Patttern第二个字符是'*'时,情况复杂：

第一个字符不匹配（除了'.'与任意字符视作匹配），那么这时'*'只能代表匹配0次，比如''ba''与''a*ba''，字符串不变，模式向后移动两个字符，然后匹配剩余字符串和模式。

第一个字符匹配，那么'*'可能代表匹配1次，多次，0次，比如"aba"与"a * ba"、 ''aaaba''与''a*ba''， ''ba''与''b*ba''。匹配1次时，字符串往后移动一个字符，模式向后移动2个字符；匹配多次时，字符串往后移动一个字符，模式不变；

【面试题19/leetcode10（正则表达式匹配|面试题19/leetcode10：正则表达式匹配 C++）】

1.递归
c code:通过

#include using namespace std; bool matchCore(char* str, char* pattern); bool match(char* str, char* pattern) { if (str == nullptr || pattern == nullptr) return false; return matchCore(str,pattern); }bool matchCore(char* str, char* pattern) { if (*str == '\0'&&*pattern == '\0') return true; if (*str != '\0'&&*pattern == '\0') return false; if (*(pattern + 1) == '*')//复杂情况 { if (*pattern == *str || (*pattern == '.' && *str != '\0')) { //分别表示匹配1次,多次,0次 return matchCore(str + 1, pattern + 2) || matchCore(str + 1, pattern) || matchCore(str, pattern + 2); } else return matchCore(str, pattern + 2); //表示匹配0次,跳过pattern‘*’ }if (*pattern == *str || (*pattern == '.' && *str != '\0'))//简单情况 return matchCore(str + 1, pattern + 1); return false; //所有情况都不满足} int main() { char str[20]; char pattern[20]; cin>>str; cin>>pattern; if (match(str, pattern)) cout << "match" << endl; else cout << "not match" << endl; return 0; }

文章图片
test c++ code递归法:

leetcode 上超出时间限制然而上述的c code可以通过
同样的算法为甚c++超时，char*比string类更加近原生层（听说STL除外，大部分c比c++快）

class Solution { public: bool isMatch(string s, string p) {if (s.empty() && p.empty()) return true; return match(s, 0, p, 0); } bool match(string s, int sIndex, string p, int pIndex){if (sIndex == (s.length()) && pIndex == (p.length()))//递归结束的条件 return true; if (p[pIndex + 1] == '*'){//复杂情况 if (p[pIndex] == s[sIndex] || (p[pIndex] == '.'&&sIndex <= (s.length() - 1))) return match(s, sIndex, p, pIndex + 2) || match(s, sIndex + 1, p, pIndex + 2) || match(s, sIndex + 1, p, pIndex); else return match(s,sIndex,p,pIndex+2); } if (p[pIndex] == s[sIndex] || (p[pIndex] == '.'&&sIndex <=(s.length() - 1)))//简单情况 return match(s, sIndex + 1, p, pIndex + 1); return false; } };

2.动态规划：
首先我们建立了一个 m*n 的二维dp矩阵，其中m表示匹配模式字符串 p 的长度，n表示待匹配字符串 s 的长度。则 dp[i][j] 表示子字符串 p[:i] 和s[:j](均包含i和j)是否匹配(true/false)。假设目前已知 dp[i][j-1] 及其前面的所有情况的匹配关系，那么要求dp[i][j]通过动态规划的递推关系如下：

1. 假如 p[i] == '.'，则dp[i][j] = dp[i-1][j-1] 2. 假如 p[i] == letter(a-zA-Z)，则dp[i][j] = dp[i-1][j-1] && (p[i]==s[j]) 3. 假如 p[i] == '*',则 dp[i][j] = dp[i-2][j] || dp[i-1][j] || (dp[i][j-1] && (p[i-1] == s[j]))

上面的1,2 均比较好理解，关键是出现 *时要分三种情况讨论，分别是 * 匹配了0个，1个，和若干个前一字符。假如匹配了0个前一字符，那么当前位置的匹配结果与dp[i-2][j]相同；匹配了1个前一字符，则当前位置的匹配结果与 dp[i-1][j]相同；关键是假如匹配了多个前一字符，该如何判断，此时我们无法知道到底匹配了多少个前一字符，但是换个角度去想这个问题，假如匹配了多个前一字符，那么前一字符要与当前的s[j]匹配（p[i-1]==s[j] 或 p[i-1]=’.’），此时要想匹配成功(dp[i][j]为true)，则当前的匹配串(p[:i])必须能够匹配s[:j-1],也就是dp[i][j-1]为true。对于这三种情况出现任意一种均可认为匹配，因此取或操作。
在具体实现中还要注意数组越界的问题，可以看到上面出现了 i-1，j-1，i-2的下标，那么在实现的时候要在原二维矩阵中各增加一行和一列，表示第0个字符也就是空字符从而避免了i-1的越界；同时只有在遇到*时才会出现i-2的下标，且这种情况下只有当*出现在匹配串第一个的时候才会越界，而当*出现在匹配串的第一个字符的时候表示为空字符串，除了待匹配字符串为空时一律为false。
C++ 动态开辟二维数组

vector>dp(m,vector(n));
bool **dp=NULL; dp = new bool *[m]; for (int i = 0; i < m; i++) { dp[i] = new bool[n]; }

c++ code : 8ms

class Solution { public: bool isMatch(string s, string p) { int m = p.length() + 1; int n = s.length() + 1; //vector>dp(m,vector(n)); bool **dp=NULL; dp = new bool *[m]; for (int i = 0; i < m; i++) { dp[i] = new bool[n]; }for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0)//初始化 { if (j == 0)dp[i][j] = true; else dp[i][j] = false; } else if (j == 0) {//i只可能是1开始 if (p[i - 1] != '*')dp[i][j] = false; else dp[i][j] = dp[i - 1][j] || dp[i - 2][j]; ////p第一个是*的，s第一个是空，短路操作不会越界，所以不能调换，细节 } else { if (p[i - 1] == '.')dp[i][j] = dp[i - 1][j - 1]; else if (p[i - 1] == '*') { if (i == 1)dp[i][j] = false; //第一个是*的其他情况 elsedp[i][j] = dp[i - 2][j] || dp[i - 1][j] || ((p[i-2]=='.'||p[i-2]==s[j-1])&&dp[i][j - 1]); } else dp[i][j] = ((s[j - 1] == p[i - 1] )&& dp[i - 1][j - 1]); } }} return dp[m - 1][n - 1]; }};

substr
C++关于 nullptr
参考1：剑指offer书----何海涛
一生不可自决
参考2