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]置为false
    for(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]);
    }
}