Another Python Backtracking, not DP


  • 2
    X
    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            if p == "" or s == "":
                return p == s or p == '*'
            i, j = 0, 0
            si, sj = -1, -1
            while True:
                if i == len(s) and j == len(p):
                    return True
                elif j != len(p) and p[j] == '*':
                    while j < len(p) and p[j] == '*':
                        j += 1
                    if j == len(p):
                        return True
                    sj = j
                    si = i
                elif i == len(s) or j == len(p) or p[j] not in ['*', '?'] and s[i] != p[j]:
                    if sj == -1 or i == len(s):
                        return False
                    si += 1
                    i = si
                    j = sj
                else:
                    i += 1
                    j += 1
    

  • 1
    Z

    learn a lot from this.


Log in to reply
 

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