LeetCode Regular Expression Matching

LeetCode Regular Expression Matching：题目、思路与代码实现。

今天尝试做一道正则表达式判断的String题目, 同时温习一下C语言的使用

题目

Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

题解

这是一段错误的代码, 其思维是线性的; 而在编译原理学正则表达式的时候,我们往往需要构建分析树, 这说明一个语言(这里当然不是指编程语言)在做正则化判断时候不能单纯线性地去考虑, 而且树的形状也应该很容易想到递归才是.

bool isMatch(char* s, char* p) {
    char last = 0;
    while(*p != 0){
        if(*p == '*'){
            if(*s == last || last == '.')
                p--;
            else
                s--;
        }
        else if(*(p+1) == '*'){
            last = *p;
            s--;
        }
        else if(*p != '.' && *p != *s){
            break;
        }
        p++;
        s++;
        
    }
    
    return (*p == 0 && *s == 0);
}

第二版本的代码如下, 采用了递归, 通过了(在几次试错之下)

bool isMatch(char* s, char* p) {
    
    // printf("test: [%s] [%s]\n", s, p);
    
    if(*p == 0 && *s == 0) return true;

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

万万没想到: 这题也是可以用动态规划来做,而且效率很高:

解析 (这个思路真的挺有深度的,值得多次回顾)

---

本文最初发布于简书。

Donate