Word Pattern II

Given apatternand a stringstr, find ifstrfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter inpatternand anon-empty substring instr.

Examples: (Note: In this problem the words in string are not separated by spaces, like the previous problem)

1. pattern ="abab", str ="redblueredblue"

   should return true.

2. pattern ="aaaa", str ="asdasdasdasd"

   should return true.

3. pattern ="aabb", str ="xyzabcxzyabc"

   should return false.

Notes: You may assume bothpatternandstrcontains only lowercase letters.

class Solution(object):
    def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
        dict = {}
        #return self.dfs(pattern, str, {})
        retVal = self.dfs(pattern, str, dict)
        '''
        for k, v in dict.iteritems():
            print 'dict: k = ', k, ' : ', v
        '''

        return retVal

    def dfs(self, pattern, str, dict):
        if len(pattern) == 0 and len(str) > 0:
            return False
        if len(pattern) == len(str) == 0:
            return True
        for end in range(1, len(str)-len(pattern)+2): # +2 because it is the "end of an end"
            if pattern[0] not in dict and str[:end] not in dict.values():
                #print 'IF: pattern[0]: ', pattern[0], ' str[:end]: ', str[:end]
                dict[pattern[0]] = str[:end]
                #print 'Will now recurse: '
                if self.dfs(pattern[1:], str[end:], dict):
                    return True
                #print 'Returned here: Will delete from dict: ', pattern[0]
                del dict[pattern[0]]
            elif pattern[0] in dict and dict[pattern[0]] == str[:end]:
                #print 'ELSE: pattern[0]: ', pattern[0], ' str[:end]: ', str[:end]
                if self.dfs(pattern[1:], str[end:], dict):
                    return True
                else:
                    return False


        return False

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