Python solution, use recursive


  • 0
    S
    1. 使用迭代,当p[1] != '*'每次判断p[0] == s[0]后令s = s[1:], p = p[1:]
    2. p[1] == '*'时特殊处理,注意 * 可以代表0到多个*之前一个的字符
    3. 注意处理边界值的情况,sp为空串时
    
    class Solution(object):
        def matchChar(self, sc, pc):
            return sc == pc or pc == '.'
    
        def isEndOfStar(self, p):
            while p != '':
                if len(p) == 1 or len(p) > 1 and p[1] != '*':
                    return False
                p = p[2:]
            return True
    
        def isMatch(self, s, p):
            if p == '':
                return s == ''
    
            if s == '':
                return self.self.isEndOfStar(p)
    
            if (len(p) > 1 and p[1] != '*') or len(p) == 1:
                # without *
                if not self.matchChar(s[0], p[0]):
                    return False
                else:
                    return self.isMatch(s[1:], p[1:])
    
            else:
                # with *
                # try see x* is empty
                if self.isMatch(s[0:], p[2:]):
                    return True
    
                # x* 可以 代表 x 一到多次
                while self.matchChar(s[0], p[0]):
                    s = s[1:]
    
                    if self.isMatch(s, p[2:]):
                        return True
    
                    if s == '':
                        return self.isEndOfStar(p)
                return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.