Regular Expression Matching

2016-04-23

问题描述

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

思路

可以采用DP，backtracking解决，一次匹配一段。本题只涉及'.','*'两个匹配符号。

Code

C语言代码

注意s的++的位置！

bool isMatch(char* s, char* p) {
    if (*p == '\0') {
        return *s == '\0';
    }
    if (*(p+1) == '*'){
        while(*p == *s || (*p == '.' && *s != '\0') ){
            if (isMatch(s++, p+2)){
                return true;
            }
        }
        return isMatch(s, p+2);
    }
    else{
        if (*p == *s || (*p == '.' && *s != '\0')){
           return isMatch(++s, p+1); 
        }
        else{
            return false;
        }
    }    
}

附加通配符匹配:leetcode 44

思路类似，同样注意s的++位置！

递归Code

bool isMatch(const char *s, const char *p) {
        if(*p == '\0') return *s == '\0';
        if(*p == '?') return isMatch(++s, ++p);
        else if (*p == '*') {
            while(*p == '*') p++; //去掉连续的‘*’
            while (*s != '\0'){
                if (isMatch(s++, p)){
                    return true;
                }
            }
            return *p == '\0';
        }
        else return *p == *s && isMatch(++ s, ++ p);
}

然而提交的时候TLE, _(:зゝ∠)_

回溯算法

递归的开销太大，所以考虑了一下回溯算法。

思路

当遇到'*'时，找到p的最近的下一个非'*'字符并标记位置，并且记录s匹配的初始位置。


if (*p == '*'){
    while(*p == '*') p++;
    startP = p;
    startS = s;
}

当*p与*s不匹配时，如果p的前面存在'*'，则进行回溯， p回到startP位置，而s = (++startS)。

Code

总体时间复杂度\(\Theta(s \times p)\)

bool isMatch(char* s, char* p) {
    
    const char *startP = NULL;
    const char *startS = NULL;
    
    while (*s){
        if (*p == *s || *p == '?'){
            ++p;
            ++s;
            continue;
        }
        
        if (*p == '*'){
            while (*p == '*') p++;
            startP = p;
            startS = s;
            
            continue;
        }
        
        if (startP != NULL){ //说明存在'*''
            p = startP;
            s = (++startS);
            
            continue;
        }
        
        return false;
        
    }
    while (*p == '*') p++;
    return *p == '\0';
}