Python backtracking solution


  • 1
    V
    class Solution(object):
        def wordPatternMatch(self, pattern, str):
            """
            :type pattern: str
            :type str: str
            :rtype: bool
            """
            pDict = dict()
            sDict = set()
            return self.helper(pattern, str, pDict, sDict)
        
        def helper(self, pattern, str, pDict, sDict):
            if len(pattern) == 0 and len(str) == 0:
                return True
            elif len(pattern) * len(str) == 0:
                return False
            
            c = pattern[0]
            if c in pDict:
                word = pDict[c]
                n = len(word)
                if len(str) < n or str[:n] != word:
                    return False
                else:
                    return self.helper(pattern[1:], str[n:], pDict, sDict)
            else:
                # backtracking
                for i in range(1, len(str) + 1):
                    word = str[:i]
                    if word not in sDict:
                        pDict[c] = word
                        sDict.add(word)
                        if self.helper(pattern[1:], str[i:], pDict, sDict):
                            return True
                        del pDict[c]
                        sDict.remove(word)
                return False

Log in to reply
 

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