Python standard backtracking with explanation

  • 0
    def wordPatternMatch(self, pattern, str):
        d = dict()
        return self.dfs(pattern, str, 0, '', d)
    def dfs(self, pattern, str, index, cur, d):
        #index is the current index of the pattern we are checking
        #cur stores the combination of new words formed by following pattern rules
        #d is a dict to store the previous letter to string correspondence
        if index >= len(pattern):
            return cur == str
        if pattern[index] in d:
            if str.startswith(cur + d[pattern[index]]):
                return self.dfs(pattern, str, index + 1, cur + d[pattern[index]], d)
            for i in range(len(cur), len(str)):
                if str[len(cur):i+1] not in d.values():
                    d[pattern[index]] = str[len(cur):i+1]
                    if self.dfs(pattern, str, index+1, cur+str[len(cur):i+1], d) == True:
                        return True
                    del d[pattern[index]]
            return False

Log in to reply

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