# 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: (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 both`pattern`and`str`contains 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/**](https://leetcode.com/problems/word-pattern-ii/)