Leetcode10-正则表达式匹配

题目链接：10. 正则表达式匹配 - 力扣（LeetCode）

这题是真的难，读懂题意就很难

首先要搞懂 “*匹配零个或多个前面的那一个元素”这句话的含义

• 第一次阅读理解可能是这样的：例如a*，匹配零个就是a，匹配一个就是aa，匹配多个就是aaaa.....
• 然而真正的含义是：匹配0次a*变为空，匹配一次变为a，匹配多次是aaaa....

 接下来说解题思路，也是看了题解才知道用动态规划

1. 定义dp[m+1][n+1]的状态数组，讲dp[0][0]初始化为true，表示空对空，能匹配上
2. 有一种特殊边界情况处理，就是当s为空（即dp[0][j]）的时候，并不是一定匹配不上。比方说，此时p为a*a*a*，将*匹配0次，就能匹配上
3. 遍历字符串，做状态转移：分两种情况

第一种情况：当s[i-1][j-1]==p[i-1][j-1]或者p[j-1] == '.'时，dp[i][j] = dp[i-1][j-1];

if (s[i-1] == p[j-1] || p[j-1] == '.') {dp[i][j] = dp[i-1][j-1];
}

第二种情况，当p[j-1] == ’*时‘，又分为两种情况

情况2.1：s[i-1] == p[j-2] || p[j-2] == '.' 时，可以匹配*前面的字符一次或多次，此时的状态转移为：dp[i][j] = dp[i-1][j];

情况2.2：上面的条件不成立，则匹配0次，此时的状态转移为：dp[i][j] = dp[i][j-2];

特别说明，应该将这两种情况结合起来，而不是对立起来。下面的代码就只能通过307 / 354，s="aaa"，p="ab*a*c*a"就通不过。因为就算情况1成立了，dp[i-1][j]也可能为false，而dp[i][j-2]为true。在这里踩了一坑。

for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s[i-1] == p[j-1] || p[j-1] == '.') {dp[i][j] = dp[i-1][j-1];} else if (p[j-1] == '*') {if (s[i-1] == p[j-2] || p[j-2] == '.') {dp[i][j] = dp[i-1][j];//匹配一个或多个}else{dp[i][j] = dp[i][j-2];//匹配0个               }}}}

最后的代码：

/*注意：dp[i][j] = dp[i-1][j]表示匹配一个或多个*/
bool isMatch(char* s, char* p) {int m = strlen(s);int n = strlen(p);bool dp[m+1][n+1];memset(dp, false, sizeof(dp));dp[0][0] = true;//比如说s为空，p为a*a*a*，能匹配成功。所以不能直接将dp[0][j]置为falsefor(int j = 1; j <=n; j++) {if (p[j-1] == '*') {dp[0][j] = dp[0][j-2];}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s[i-1] == p[j-1] || p[j-1] == '.') {dp[i][j] = dp[i-1][j-1];} else if (p[j-1] == '*') {if (j > 1) {dp[i][j] = dp[i][j-2];//匹配0个 if (s[i-1] == p[j-2] || p[j-2] == '.') {dp[i][j] = dp[i][j] || dp[i-1][j];//匹配一个或多个}}}}}return dp[m][n];
}

还可以用递归的方法，理解起来感觉简单一些

bool isMatch(char* s, char* p) {if(strlen(s) == 0){if (strlen(p) == 0){return true;}if (p[1] == '*') {return isMatch(s, &p[2]);}return false;}bool first_match = (s != NULL && (s[0] == p[0] || p[0] == '.'));if(strlen(p) >= 2 && p[1] == '*') {return isMatch(s, &p[2]) || (first_match && isMatch(&s[1], p));}else{return first_match && isMatch(&s[1], &p[1]);}
}