Python standard backtracking with explanation


  • 0
    W
    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)
        else:
            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.