Description

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.(i.e if a corresponds to s, then b cannot correspond to s. For example, given pattern = "ab", str = "ss", return false.)

Example

Input:
pattern = "abab"
str = "redblueredblue"
Output: true
Explanation: "a"->"red","b"->"blue"

Solution

class Solution:
    """
    @param pattern: a string,denote pattern string
    @param str: a string, denote matching string
    @return: a boolean
    """
    def match_dict(self,s,i,p,j):
        if i ==len(s) and j !=len(p):
            return False
        if i == len(s) and j==len(p):
            return True
        if s[i] in self.dict:
            # 判断是否为开头，是则继续搜索
            if not p[j:].startswith(self.dict[s[i]]):
                return False
            return self.match_dict(s,i+1,p,j+len(self.dict[s[i]]))
        else:
            for k in range(j,len(p)):
                val = p[j:k+1]
                
                if val in self.used_source_word:
                    continue # has been discussed before
                
                self.dict[s[i]] = val
                self.used_source_word.add(val)
                if self.match_dict(s,i+1,p,k+1):
                    return True
                # continue find 
                del self.dict[s[i]]
                self.used_source_word.remove(val)
            return False
    def wordPatternMatch(self, pattern, str):
        # write your code here
        self.dict = {}
        self.used_source_word = set()
        return self.match_dict(pattern,0,str,0)