题解 | #正则表达式匹配#

C++递归

bool match(string str, string pattern) {
    int str_length = str.size();
    int p_len = pattern.size();
    // base case
    if(str.empty()){
        if(p_len%2 != 0 )
            return false;
        else{
            if(p_len == 0)
                return true;
            int i = 1;
            while(i< p_len){
                if(pattern[i] != '*')
                    return false;
                i=i+2;
            }
            return true;
        }
    }
    if (pattern.empty())
        return false;
    char c_s = str[0];
    char c_pat = pattern[0];
    char c_star = 's';

    if (p_len>=2)
        c_star = pattern[1];
    //normal case
    if( c_star != '*' )
    {
        if(c_s == c_pat|| c_pat == '.')
            return match(str.substr(1, str_length-1), pattern.substr(1, p_len-1));
    }
    else
    {
        // ignore '*'
        if(c_s == c_pat|| c_pat == '.'){
        return match(str, pattern.substr(2, p_len-2))
            ||match(str.substr(1,str_length-1), pattern);

        }

        //else
        else{
            return match(str, pattern.substr(2, p_len-2));
        }

    }
    return false;
}