leetcode-Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

AC Code：以下是brute force DFS搜索AC的从code。由于LeetCode有一个很长的不能break的测试用例，因此把word break I 判断能否break的函数作为sub routine，先判断一下能否break，如果不能直接返回空容器。

``` 1 public class Solution {
2     public List<String> wordBreak(String s, Set<String> dict) {
3         ArrayList<String> res = new ArrayList<String>();
4         if(s == null || s.isEmpty() || !wordBreakCanDo(s, dict)){
5             return res;
6         }
7         dfs(s, dict, 0, "", res);
8         return res;
9     }
10
11     //10:08
12     public void dfs(String s, Set<String> dict, int startIndex, String preWords, ArrayList<String> res){
13         if(startIndex >= s.length()){
14             //return contition is that the startIndex has been out of bound
16             return;
17         }
18         for(int i = startIndex; i < s.length(); i++){
19             String curStr = s.substring(startIndex, i+1);
20             if(dict.contains(curStr)){
21                 String newSol;
22                 if(preWords.length() > 0){
23                     newSol = preWords + " " + curStr;
24                 } else {
25                     newSol = curStr;
26                 }
27                 dfs(s, dict, i + 1, newSol, res);
28             }
29         }
30     }
31     //1021
32
33     public boolean wordBreakCanDo(String s, Set<String> dict) {
34         s = "#" + s;
35         boolean[] canSegmented = new boolean[s.length()];
36
37         canSegmented[0] = true;
38         for(int i = 1; i < s.length(); i++){
39             for(int k = 0; k < i; k++){
40                 canSegmented[i] = canSegmented[k] && dict.contains(s.substring(k + 1, i + 1));
41                 if(canSegmented[i]) break;
42             }
43         }
44         return canSegmented[s.length() - 1];
45     }
46 }  ```

leetcode-Word Break II

(0)
(0)

0条