题目描述

给定一个pattern和一个字符串str，查找str是否遵循相同的模式。

这里遵循的意思是一个完整的匹配，在一个字母的模式和一个非空的单词str之间有一个双向连接的模式对应。(如果a对应s，那么b不对应s。例如，给定的模式= "ab"， str = "ss"，返回false）。

测试样例

输入:

pattern = "abab"

str = "redblueredblue"

输出: true

说明: "a"->"red","b"->"blue"

输入:

pattern = "aaaa"

str = "asdasdasdasd"

输出: true

说明: "a"->"asd"

输入:

pattern = "aabb"

str = "xyzabcxzyabc"

输出: false

解题思路

题目意思就是将pattern中每种类型的字符映射到str中的一种子串，同时两者的顺序要对应一致。于是，可以对pattern和str采取同步递归的方式进行处理。

所谓“同步”，即pattern每取出一个字符，就映射到str的一个前缀子串，然后再对pattern和str后面的部分进行搜索。由于是同步的，那么当pattern取完所有字符时，自然也要求str为空。

另外，由于pattern中有重复的字符，因此需要记录这些字符与str的前缀子串的映射关系。在搜索过程中，若当前取出的pattern中的字符已记录在这映射关系中，我们就可以直接根据映射关系取出对应的str的前缀子串。进一步，若此时取出的不是当前str的前缀子串，那么就返回False。

到目前为止，还没有提到如何将pattern中的字符与str的前缀子串进行映射。方法很简单，很粗暴，就是穷举str的每个前缀子串，每得到一种映射方案后就对pattern和str后面的部分进一步搜索。在穷举过程中，若当前str的前缀子串已在先前被pattern的其它字符映射，那么就不采取这种映射方式，继续搜索下一个前缀子串看是否可行，于是在穷举过程中我们还需要对前缀子串进行标记。

代码

class Solution:

    """

    @param pattern: a string,denote pattern string

    @param str: a string, denote matching string

    @return: a boolean

    """

    def wordPatternMatch(self, pattern, str):

        return self._match(pattern, str, {}, set())

    def _match(self, p, s, mapping, used):

        # pattern每拿掉一个字符，

        # 都映射到str的一个前缀子串

        # 因此若pattern已取完所有字符，

        # 则要求str也为空

        if not p:

            return not s

        char = p[0]

        word = mapping.get(char)

        # 若当前在pattern取出的字符已被记录在映射关系中

        # 则直接根据映射关系取出对应到str的子串

        if word:

            # 这个子串必须是str的prefix

            if not s.startswith(word):

                return False

            return self._match(p[1:], s[len(word):], mapping, used)

        # 对于当前取出的pattern字符

        # 采取穷举映射的方法进行搜索

        for i in range(1, len(s) + 1):

            word = s[:i]

            # 若当前搜索到的str的prefix已被pattern的其它字符映射

            # 则跳过

            if word in used:

                continue

            used.add(word)

            mapping[char] = word

            if self._match(p[1:], s[i:], mapping, used):

                return True

            used.remove(word)

            del mapping[char]

        return False