139.-word-break.md

139. Word Break

{% tabs %} {% tab title="wordset based" %}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wd = set(wordDict)
        visited = [-1] * len(s)
        return self.dfs(0, s, wd,visited)
    
    def dfs(self, idx , s , wd, v):
        if idx == len(s):
            return True
        
        if v[idx] != -1:
            return v[idx]
        
        for w in wd:
            ls = len(w)
            if s[idx: idx + ls] == w and self.dfs(idx + ls, s , wd,v):
                v[idx] = 1
                return True
        v[idx] = 0
        return False

{% endtab %}

{% tab title="DFS" %}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wd = set(wordDict)
        visited = [-1] * len(s)
        return self.dfs(0, s, wd,visited)
        
    def dfs(self, idx, s,wd,visited):
        if idx == len(s):
            return True
        if visited[idx] != -1:
            return visited[idx]
        
        for i in range(idx+1,len(s)+1): 
            if (s[idx:i] in wd) and self.dfs(i,s,wd,visited):
                visited[idx] = 1
                return True
        visited[idx] = 0
        return False
    
        

{% endtab %}

{% tab title="BFS" %}

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s:
            return False
        
        wd = set(wordDict)
        visited = [0] * len(s)
        ## 這題就是 真假, 找不着得到東西
        
        q = collections.deque()
        q.append(0)
        while q:
            node = q.popleft() ## 換一下又是DFS
            if visited[node] == 1:
                continue
            
            for i in range(node+1,len(s)+1):
                if s[node:i] in wd:
                    q.append(i)
                    
                    ## 恰巧走到最後 
                    if i == len(s):
                        return True
            ## 成功掃描完畢
            visited[node] = 1
            
        return False

{% endtab %} {% endtabs %}