140.-word-break-ii.md

140. Word Break II

{% tabs %} {% tab title="Python" %}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:

        wd = set(wordDict)  
        res = []
        memo = [1] * (len(s) + 1)
        self.dfs(0, s, wd, [], res,memo)
        return res


# 这才是自己的做法
    def dfs(self, idx, s, wd, path, res,memo):
        num = len(res)
        if idx == len(s):
            res.append(" ".join(path[:]))
            return

        for i in range(idx, len(s) + 1):
        ## 这里不能遍历wd，会造成重复！
            if  memo[i] and s[idx:i] in wd:
                path.append(s[idx:i])
                self.dfs(i, s , wd, path , res,memo)
                path.pop()

            memo[idx] = 1 if len(res) > num else 0

{% endtab %}

{% tab title="Python" %}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        ## 就是打印路徑 
        wd = set(wordDict)
        ## 重點,二維數組表示記錄, 好啦 要邁向DP了 
        visited = [[-1] * len(s) for _ in range(len(s))]
        res = []
        self.dfs(0, s, res, [], wd, visited)
        return res
        
    def dfs(self, idx, s, res,  path, wd, visited):
        
        if idx == len(s):
            res.append(" ".join(path[:]))
            return 
        
        for i in range(idx + 1, len(s) + 1):
            if visited[idx][i-1] == 0:
                return
            if s[idx:i] not in wd:
                visited[idx][i-1] == 0
            elif s[idx:i] in wd and visited[idx][i-1] == -1:
                visited[idx][i-1] == 1 
                path.append(s[idx:i])
                self.dfs(i, s, res, path, wd, visited)
                path.pop()
                visited[idx][i-1] == -1
	## 典型的所有技巧都用上, 都被暴打.....

{% endtab %}

{% tab title="优化" %}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        ## 就是打印路徑 
        wd = set(wordDict)
        res = {}
        ans = self.dfs(s, res, wd)
        return list(map(lambda x: x.strip(),ans))
        
    def dfs(self, s, res, wd):
        
        if s in res.keys():
            return res[s]
        if s == "": # 類比到了葉子,返回葉子value,爲什麼是[]? 因爲遞歸函數定義就是返回list
            return [""]
        path = []
        for w in wd:
            if s[:len(w)] != w:
                continue
            left = self.dfs(s[len(w):],res,wd)
            for sub in left:
                path.append(w + " " + sub)
        res[s] = path
        return res[s]
    
    ##　對於　經典例子　ａａａａａ　這裏便利ｗｏｒｄｄｉｃｔ，剪得明顯．

{% endtab %} {% endtabs %}