10.正则匹配

实现一个支持’.’和’*’的正则表达式

• ‘.’:匹配任意单个字符。

• ‘*’:匹配0个或多个前导字符。

• 匹配需要包含整个输入字符串，不能是部分。

函数原型如下:

bool isMatch(const char *s, const char *p)

def isMatch(s, p):  
    if len(p) == 0:  
        return len(s) == 0  
  
    if len(p) == 1:  
        return len(s) == 1 and (s[0] == p[0] or p[0] == '.')  
  
    if p[1] != '*':  
        if len(s) > 0 and (s[0] == p[0] or p[0] == '.'):  
            return isMatch(s[1:], p[1:])  
        else:  
            return False  
    while len(s) > 0 and (s[0] == p[0] or p[0] == '.'):  
        if isMatch(s, p[2:]): #match 1 or many times  
            return True  
        s = s[1:] #match many times.  

    return isMatch(s, p[2:]) #match 0 times.  

if __name__ == "__main__":  
    print(isMatch("abcdd", "a*bcd*"))  
    print(isMatch("aab", "c*a*b"))