Regular Expression Matching
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
Method
If the s and p the first letter are the same or p’s first letter is “.”, it can be both removed away.
So the most difficult situation is when the p’s first is “*”.
Since the * must follow’s one letter. So we think about p two by two. One letter will follows a “*”.
In the s, there are several situation that will match a letter following a “*”. So we need to remove all these same letter.
Python code
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(p) == 0: return len(s) == 0
if len(p) == 1 or p[1] != "*":
if len(s) == 0 or (p[0] != s[0] and p[0] !="."):
return False
return self.isMatch(s[1:],p[1:])
else:
i = -1
length = len(s)
while i < length and (i<0 or p[0] == "." or p[0] == s[i]):
if self.isMatch(s[1+i:],p[2:]): return True
i = i + 1
return False
近期评论