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"].

[解题思路]

DFS + backtracking

在大数据："aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

挂掉了

 1  public static ArrayList<String> wordBreak(String s, Set<String> dict) {
 2         // Note: The Solution object is instantiated only once and is reused by
 3         // each test case.
 4         ArrayList<String> result = new ArrayList<String>();
 5         if (s == null || s.length() == 0) {
 6             return result;
 7         }
 8         int length = s.length();
 9         dfs(s, 0, 0, length, dict, result, new StringBuffer());
10         return result;
11     }
12 
13     public static void dfs(String s, int start, int depth, int length,
14             Set<String> dict, ArrayList<String> result, StringBuffer sb) {
15         if (depth == length) {
16             String t = sb.toString();
17             result.add(t.substring(0, t.length() - 1));
18             return;
19         }
20 
21         for (int len = 1; len <= length - start; len++) {
22             String t = s.substring(start, start + len);
23             if (dict.contains(t)) {
24                 int beforeAddLen = sb.length();
25                 sb.append(t).append(" ");
26                 dfs(s, start + len, depth + len, length, dict, result, sb);
27                 sb.delete(beforeAddLen, sb.length());
28             }
29         }
30     }

2.DP+DFS

使用Word Break对字符串进行处理，处理结束后使用DFS进行DFS

 1 public class Solution {
 2     public static ArrayList<String> wordBreak(String s, Set<String> dict) {
 3         ArrayList<String> result = new ArrayList<String>();
 4         if (s == null || dict.size() <= 0) {
 5             return result;
 6         }
 7         int length = s.length();
 8         // seg(i, j) means substring t start from i and length is j can be
 9         // segmented into
10         // dictionary words
11         boolean[][] seg = new boolean[length][length + 1];
12         for (int len = 1; len <= length; len++) {
13             for (int i = 0; i < length - len + 1; i++) {
14                 String t = s.substring(i, i + len);
15                 if (dict.contains(t)) {
16                     seg[i][len] = true;
17                     continue;
18                 }
19                 for (int k = 1; k < len; k++) {
20                     if (seg[i][k] && seg[i + k][len - k]) {
21                         seg[i][len] = true;
22                         break;
23                     }
24                 }
25             }
26         }
27         if (!seg[0][length]) {
28             return result;
29         }
30 
31         int depth = 0;
32         dfs(s, seg, 0, length, depth, result, new StringBuffer(), dict);
33 
34         return result;
35     }
36 
37     private static void dfs(String s, boolean[][] seg, int start, int length,
38             int depth, ArrayList<String> result, StringBuffer sb, Set<String> dict) {
39         if (depth == length) {
40             String t = sb.toString();
41             result.add(t.substring(0, t.length() - 1));
42             return;
43         }
44 
45         for (int len = 1; len <= length; len++) {
46             if (seg[start][len]) {
47                 String t = s.substring(start, start + len);
48                 if(!dict.contains(t)){
49                     continue;
50                 }
51                 int beforeAddLen = sb.length();
52                 sb.append(t).append(" ");
53                 dfs(s, seg, start + len, length, start + len, result, sb, dict);
54                 sb.delete(beforeAddLen, sb.length());
55             }
56         }
57     }
58 }