首页 > 代码库 > LeetCode 010 Regular Expression Matching

LeetCode 010 Regular Expression Matching

2024-07-04 11:42:50   216人阅读

【题目】


Implement regular expression matching with support for ‘.‘ and ‘*‘.

‘.‘ Matches any single character.
‘*‘ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true


【题意】

题意匹配字符串和正则模式串，只考虑"."和"*"


【思路1】

    本题与wildcard matching那道题不同，方法不通用
    本题的关键在于确定每个*需要匹配多少字符
    使用DFS方法来做


【代码】

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int sLen=strlen(s);
        int pLen=strlen(p);
        if(sLen==0 && pLen==0)return true;
        if(sLen!=0 && pLen==0)return false;
        if(sLen==0 && pLen==1)return false;   //*都是和一个字符成对出现，p长度为1表明不可能再有*
        
        if(p[1]==‘*‘){
            if(p[0]==‘.‘){
                int k=0;    //*匹配的字符数
                while(k<=sLen){
                    if(isMatch(s+k, p+2))return true;
                    k++;
                }
            }
            else{
                int k=0;    //*匹配的字符数
                while(k<=sLen && s[k]==p[0]){
                    if(isMatch(s+k, p+2))return true;
                    k++;
                }
                if(isMatch(s+k, p+2))return true;
            }
        }
        else{
            if(sLen==0)return false;        //注意"" "..*"这种特殊的情况
            else if(p[0]==‘.‘ || s[0]==p[0])
                return isMatch(s+1, p+1);
        }
        return false;
    }
};


联系
我们