291. Word-Pattern-II.md

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-emptysubstring in str.

Example 1:

Input: pattern = "abab", str = "redblueredblue"
Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false

Notes: You may assume both pattern and str contains only lowercase letters.

---

python solution

这道题很有意思，难度为Difficult，但只要思路清晰，还是不难的。

首先我们要确定使用什么算法。

对于pattern = "abab", str = "redblueredblue"，假如你是笨笨的计算机，你会怎么做？最直观的就是一个一个的尝试a了，例如a=r,a=re, a=red, a=redb,a=redbl,a=redblu...

很快就能想到使用DFS，在判断过程中如果失败就退回到之前的状态再进行其他递归判断。

class Solution(object):

    def __init__(self):
        self.res = False

    def wordPatternMatch(self, pattern, string):
        """
        :type pattern: str
        :type string: str
        :rtype: bool
        """

        # DFS
        def dfs(pattern, string, patternDict):  # patternDict一个字典，
            if not string and not pattern: # 此时说明pattern匹配
                self.res = True
                return
            if string and pattern: # 如果pattern和string中都还有字符，继续进行判断
                if pattern[0] in patternDict.keys():  # pattern已存储于字典中
                    if string.startswith(patternDict[pattern[0]]):  # 当前string开头匹配已有的pattern
                        dfs(pattern[1:], string[len(patternDict[pattern[0]]):], patternDict)
                    else: # 字符对应的字符串与当前string开头不匹配，肯定不行。
                        return
                else:
                    for i in range(1, len(string) + 1): #尝试所有可能的构造字符串
                        if string[:i] not in patternDict.values():
                            dfs(pattern[1:], string[i:], dict(**patternDict,**{pattern[0]:string[:i]}))

        dfs(pattern, string, {})
        return self.res


print(Solution().wordPatternMatch("abba", "dogcatcatdog"))

• 做了一个全局的res，在判断过程中，只要有一个pattern满足条件，就把这个变量置为True

• 使用一个patternDict保存字符对应的字符串，如果后面遇到相同的字符，则直接从中取出相应的字符串，岂不美哉？如果当前的字符没有存储到这个字典中，那么我们就尝试所有可能的字符串。

• 其中难以理解的在于第27行：

  dfs(pattern[1:], string[i:], dict(**patternDict,**{pattern[0]:string[:i]}))
  

  这是python3中合并字典的方法，将两个已有的字典合并成一个新的字典。

  但为什么不用下面这种更简单的方式呢，看上去多直观啊！

  if string[:i] not in patternDict.values():
  	patternDict[pattern[0]] = string[:i]
  	dfs(pattern[1:], string[i:], patternDict)
  

  其实一开始我也是这样写的，但过不了所有测试用例，后来调试发现，这样会将patternDict给污染掉，在其他递归中，patternDict会被当前递归的结果给污染。这是DFS遍历一定要注意的问题，其实pattern和string变量也是一样的，我们都是直接传值，而不是先更改再传值，例如：

  if string[:i] not in patternDict.values():
      string = string[i:]
      pattern=pattern[1:]
  	patternDict[pattern[0]] = string[:i]
  	dfs(pattern, string, patternDict)
  

  这样写更糟糕，会把string和pattern一起污染。为什么会出现这种问题呢？因为局部string变量和全局string其实是共享一个内存空间的，千万不要使用相同的命名。如果这样写是没问题的：

  if string[:i] not in patternDict.values():
      newString = string[i:]
      newPattern = pattern[1:]
      dfs(newPattern, newString, dict(**patternDict, **{pattern[0]: string[:i]})