题目

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

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isMatch(self, s, p):
if s == p:
return True
if len(p) == 0 and len(s) > 0:
return False
firstMatch = len(s) > 0 and p[0] in {s[0], '.'}
if len(p) >= 2 and p[1] == '*':
return firstMatch and self.isMatch(s[1:], p) or self.isMatch(s, p[2:])
else:
return firstMatch and self.isMatch(s[1:], p[1:])