首页 > itarticle > leetcode 010

leetcode 010

admin 11月 13, 2020 0

Regular Expression Matching
Method
Python code

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