正则表达式匹配 - 递归

谁践踏了优雅 2022-12-19 00:50 187阅读 0赞

## 正则表达式匹配 ##

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

**示例 1:**

输入:
    s = "aa"
    p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串。

**示例 2:**

输入:
    s = "aa"
    p = "a*"
    输出: true
    解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

**示例 3:**

输入：
    s = "ab"
    p = ".*"
    输出: true
    解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

**示例 4:**

输入:
    s = "aab"
    p = "c*a*b"
    输出: true
    解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

**示例 5:**

输入:
    s = "mississippi"
    p = "mis*is*p*."
    输出: false
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

## 解法(递归) ##

bool isMatch(char* s, char* p){ 
        if(s == NULL || p == NULL)
            return false;
        // 使用递归的方式
        if(*s == '\0' && *p == '\0')
            return true;
        // 1.如果 *s != '\0' *p == '\0'
        if(*s != '\0' && *p == '\0')
            return false;
        // 2. 直接判断*(p+1)是否是*，如果是，则是这些情况：当前是str * / . *
        if(*(p + 1) == '*'){ 
            if(*p == *s || (*p == '.' && *s != '\0')){ 
                // 1. *p不为空的情况且不为.的情况：
                // *p == *s(只有一种情况) -> *p != '\0' && *s != '\0'
                // *p != *s(两种情况) -> *p一定不为空：(*s == '\0' || *s != '\0')
                // 2. *p为.的情况
                // *s 为空，当*s为空时，有种特殊情况，就是*(p+2)不为空的情况，此时不成立
                // *s 不空，此时可以成立 
    
                // (*p == '.' && *s != '\0')原因在此，加入*s == '\0'，不可以执行下面的s+1
                // *p == *s 这里已经保证了*s不为空；
                return isMatch(s+1,p+2) || isMatch(s,p+2) || isMatch(s+1,p);
            }else{ 
                return isMatch(s,p+2);
            }
        }else{ 
            if(*p == *s || (*p == '.' && *s != '\0')){ 
                return isMatch(s+1,p+1);
            }else{ 
                return false;
            }
        }
    
    }