Word Pattern II

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

Space

class Solution:

    def wordPatternMatch(self, pattern, string):
        return self.dfs(pattern, string, dict())

    def dfs(self, pattern, string, charsToWords):
        bijectionNotPossible = len(pattern) == 0 and len(string) > 0
        if bijectionNotPossible:
            return False

        isMatched = len(pattern) == len(string) == 0
        if isMatched:
            return True

        endOfEnd = len(string) - len(pattern) + 2

        for endIdx in range(1, endOfEnd):
            curChar = pattern[0]
            matchingWord = string[:endIdx]

            curCharMapsToOtherWord = curChar in charsToWords and charsToWords[curChar] != matchingWord
            matchingWordMapsToOtherChar = curChar not in charsToWords and matchingWord in charsToWords.values()
            curCharMapsToMatchingWord = curChar in charsToWords and charsToWords[curChar] == matchingWord

            if curCharMapsToOtherWord or matchingWordMapsToOtherChar:
                continue

            if curChar not in charsToWords and matchingWord not in charsToWords.values():
                charsToWords[curChar] = matchingWord

                if self.dfs(pattern[1:], string[endIdx:], charsToWords):
                    return True

                del charsToWords[curChar]

            elif curCharMapsToMatchingWord:
                if self.dfs(pattern[1:], string[endIdx:], charsToWords):
                    return True

        return False

Learn

#Backtracking

#Hash Table

#Bijection

Videos