[leetcode/lintcode 題解] 阿裡面試題：字模式II

描述

給定一個pattern和一個字元串str，查找str是否遵循相同的模式。

這裡遵循的意思是一個完整的比對，在一個字母的模式和一個非空的單詞str之間有一個雙向連接配接的模式對應。(如果a對應s，那麼b不對應s。例如，給定的模式="ab"， str ="ss"，傳回false）。

線上評測位址：

領扣題庫官網

樣例1
輸入:
pattern = "abab"
str = "redblueredblue"
輸出: true
說明: "a"->"red","b"->"blue"           

樣例2
輸入:
pattern = "aaaa"
str = "asdasdasdasd"
輸出: true
說明: "a"->"asd"           

樣例3
輸入:
pattern = "aabb"
str = "xyzabcxzyabc"
輸出: false           

用

九章算法班

中講過的深度優先搜尋算法。 這個題不能使用動态規劃或者記憶化搜尋，因為參數清單中 mapping 和 used 無法記錄到記憶化的哈希表中。

class Solution:
    """
    @param pattern: a string,denote pattern string
    @param str: a string, denote matching string
    @return: a boolean
    """
    def wordPatternMatch(self, pattern, string):
        return self.is_match(pattern, string, {}, set())

    def is_match(self, pattern, string, mapping, used):
        if not pattern:
            return not string
            
        char = pattern[0]
        if char in mapping:
            word = mapping[char]
            if not string.startswith(word):
                return False
            return self.is_match(pattern[1:], string[len(word):], mapping, used)
            
        for i in range(len(string)):
            word = string[:i + 1]
            if word in used:
                continue
            
            used.add(word)
            mapping[char] = word
            
            if self.is_match(pattern[1:], string[i + 1:], mapping, used):
                return True
            
            del mapping[char]
            used.remove(word)
            
        return False           

更多題解參考：

九章官網solution