# 0139. Word Break
###### tags: `Leetcode` `Medium` `Dynamic Programming` `BFS`
Link: https://leetcode.com/problems/word-break/
## 思路
### 思路一 $O(N^3)$
动态规划
**注意List可以直接转换成Set的写法
以及substring的用法 substring(start,end)是取s[start]到s[end-1]**
### 思路二 $O(N^3)$
BFS/DFS+memo
时间复杂度分析:因为对于每一个位置，都要把后面的所有位置全部找一遍，找的过程中，产生substring $O(N)$
## Code
### 思路一

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 1; i <= s.length();i++){
            for(int j = 0;j < i;j++){
                dp[i] = dp[j]&&wordDictSet.contains(s.substring(j,i));
                if(dp[i]) break;
            }
        }
        return dp[s.length()];
    }
}

### 思路二 dfs+memo

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        visited = [False]*len(s)
        def dfs(start):
            if start == len(s): return True
            if visited[start]: return False
            visited[start] = True
            
            for word in wordDict:
                if s[start:].startswith(word):
                    if dfs(start+len(word)):
                        return True
            return False

        return dfs(0)   

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] visited = new boolean[s.length()];
        return dfs(s, wordDict, visited, len);
    }
    private boolean dfs(String s, List<String> wordDict, boolean[] visited, int len){
        if(s.length()==0) return true;
        if(visited[len-s.length()]) return false;       
        for(String word:wordDict){
            if(s.startsWith(word)){
                if(dfs(s.substring(word.length()), wordDict, visited, len)) return true;
            }
        }
        visited[len-s.length()] = true;
        return false;
    }
}

### 思路三 bfs+memo

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Queue<Integer> q = new LinkedList<Integer>();
        Set<String> dict = new HashSet<String>(wordDict);
        boolean[] visited = new boolean[s.length()];
        q.add(0);
        while(!q.isEmpty()){
            int start = q.poll();
            if(visited[start]) continue;
            for(int end = start+1;end <= s.length();end++){
                if(dict.contains(s.substring(start,end))){
                    q.add(end);
                    if(end == s.length()){
                        return true;
                    }
                }
            }
            visited[start] = true;
        }
        return false;
    }
}