Fast Python solution with backtracking and caching + DP solution


  • 21
    C

    Takes about 174ms:

    cache = {}
    def isMatch(self, s, p):
        if (s, p) in self.cache:
            return self.cache[(s, p)]
        if not p:
            return not s
        if p[-1] == '*':
            if self.isMatch(s, p[:-2]):
                self.cache[(s, p)] = True
                return True
            if s and (s[-1] == p[-2] or p[-2] == '.') and self.isMatch(s[:-1], p):
                self.cache[(s, p)] = True
                return True
        if s and (p[-1] == s[-1] or p[-1] == '.') and self.isMatch(s[:-1], p[:-1]):
            self.cache[(s, p)] = True
            return True
        self.cache[(s, p)] = False
        return False
    

    DP version:

    def isMatch(self, s, p):
        dp = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]
        dp[0][0] = True
        for i in range(1, len(p)):
            dp[i + 1][0] = dp[i - 1][0] and p[i] == '*'
        for i in range(len(p)):
            for j in range(len(s)):
                if p[i] == '*':
                    dp[i + 1][j + 1] = dp[i - 1][j + 1] or dp[i][j + 1]
                    if p[i - 1] == s[j] or p[i - 1] == '.':
                        dp[i + 1][j + 1] |= dp[i + 1][j]
                else:
                    dp[i + 1][j + 1] = dp[i][j] and (p[i] == s[j] or p[i] == '.')
        return dp[-1][-1]

  • 0
    Z
    This post is deleted!

  • 0
    S

    One question about the DFS method. I have a idea to cache index pairs instead of string pairs. And convert string to char array first. Because I think string is immutable, caching them take much space. Is it a good idea or it's just the same thing.


  • 0
    C

    I think string is fine, converting to char array will cause overhead


  • 0
    S

    Thank you for replying and explaining to me. I got it.


  • 0
    F

    It seems pure recursion should work for the first version. Is the cache only used limit the space used?


  • 0
    F

    I have just found out the answer after studying more about dynamic programming. Thank you for the great answer for the problem.


  • 0
    Z

    Thank you for sharing

    The first solution did not consider the case "**" or even longer exist.

    For example, "aaa", "abaca" return true, but "aaa", "abac***a" return false. (OJ seems to have no such test)

    Solution 2 is great.


  • 0
    Z
    
    class Solution(object):
        def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            if s == None or p == None:
                return False
            
            dp = [[False for i in range(len(p) + 1)] for i in range(len(s) + 1)]
                
            dp[0][0] = True
            for j in range(2, len(dp[0])):
                if p[j-1] == '*':
                    dp[0][j] = dp[0][j-2]
                    
            for i in range(1, len(dp)):
                for j in range(1, len(dp[0])):
                    if s[i-1] == p[j-1] or p[j-1] == '.':
                        dp[i][j] = dp[i-1][j-1]
                    elif p[j-1] == '*':
                        if p[j-2] != s[i-1] and p[j-2] != '.':
                            dp[i][j] = dp[i][j-2]
                        else:
                            dp[i][j] = dp[i-1][j] | dp[i][j-1] | dp[i][j-2]
                            
            return dp[len(s)][len(p)]
    

  • 0

    Instead of storing it within a table, it could just use an array:
    ~68ms:

    class Solution(object):
        def isMatch(self, s, p):
            prev = [False, True]
            for j in range(len(p)):
                prev.append(p[j]=='*' and prev[j])
    
            for i in range(len(s)):
                curr = [False, False]
                for j in range(len(p)):
                    if p[j]=='*':
                        curr.append(curr[j] or curr[j+1] or (prev[j+2] and p[j-1] in (s[i], '.')))
                    else:
                        curr.append(prev[j+1] and p[j] in (s[i], '.'))
                prev = curr
            return prev[-1]
    

Log in to reply
 

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