291 Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples: pattern = "abab", str = "redblueredblue" should return true. pattern = "aaaa", str = "asdasdasdasd" should return true. pattern = "aabb", str = "xyzabcxzyabc" should return false. Notes: You may assume both pattern and str contains only lowercase letters.

https://leetcode.com/problems/word-pattern-ii/

class Solution(object):
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        return self.bt(pattern, str, {})

    def bt(self, pattern, s, d):
        if not pattern and len(s)>0:
            return False
        if not pattern and not s:
            return True

        for i in range(len(s)-len(pattern)+1):
            if pattern[0] in d and d[pattern[0]]==s[:i+1]:
                if self.bt(pattern[1:], s[i+1:], d):
                    return True
            elif pattern[0] not in d and s[:i+1] not in d.values():
                d[pattern[0]] = s[:i+1]
                if self.bt(pattern[1:], s[i+1:], d):
                    return True
                del d[pattern[0]]
        return False