題目出處

829 · Word Pattern II

難度

hard

個人範例程式碼

class Solution:
    """
    @param pattern: a string,denote pattern string
    @param str: a string, denote matching string
    @return: a boolean
    """
    def word_pattern_match(self, pattern: str, str: str) -> bool:
        # write your code here
        self.pattern_to_str = {}
        self.str_to_pattern = {}

        return self.dfs(pattern, str, 0)

    def dfs(self, pattern, str, start):
        # print(pattern, start, self.pattern_to_str)
        # end of recursion
        if not pattern:
            if start == len(str):
                return True
            return False

        # define and split
        # match pattern
        if pattern[0] in self.pattern_to_str:
            match_pattern = self.pattern_to_str[pattern[0]]
            end_idx = start + len(match_pattern)
            if end_idx <= len(str) and match_pattern == str[start:end_idx]: 
                return self.dfs(pattern[1:], str, end_idx) # to end_idx-1, from end_idx
            else: # pattern not match 
                return False

        # find next word
        for i in range(start+1, len(str)+1):
            substr = str[start:i] # to i-1
            if substr in self.str_to_pattern:
                if not self.str_to_pattern[substr] == pattern[0]: # match to another character
                    continue # find next
            else: # add new word
                self.pattern_to_str[pattern[0]] = substr
                self.str_to_pattern[substr] = pattern[0]
                if self.dfs(pattern[1:], str, i): # to i-1, from i
                    return True

                # backtracking
                del self.pattern_to_str[pattern[0]]
                del self.str_to_pattern[substr]

        return False

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

• 這題與前一題的差別為，前一題已經都幫忙把 string 切好了，而這題目連切都要自己切，還考了怎麼切：

【Leetcode】python – [290] Word Pattern 個人解法筆記

這題我們透過 dfs 的方式不斷的去進行往下的切割，直到完成

注意要判斷是否結束字時 pattern 已經使用完

有一種特殊狀況是 “aaa” 與 “aaaa”

如果沒有特別處理，容易會漏掉最後一個配對，卻回傳 True。

這邊我們是判斷 start = len(str)，因為我們的 start 會不斷移動，
最後當移動超過範圍時。就是找到了正確結果的情況下，結束了我們的配對任務。

input handling

x

Boundary conditions

上方說明了，當 DFS 的 start point 超過了可搜尋範圍，就結束 DFS。

Reference

• 字模式 II · Word Pattern II