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"].
二维DP +ＤＦＳ：
1 public class Solution { 2 int len = 0; 3 boolean[][] map = null; 4 ArrayList<String> al = null; 5 public ArrayList<String> wordBreak(String s, Set<String> dict) { 6 // Note: The Solution object is instantiated only once and is reused by each test case. 7 al = new ArrayList<String>(); 8 if(s == null || s.length() == 0) return al; 9 len = s.length(); 10 map = new boolean[len][len + 1]; 11 for(int i = len - 1; i > -1; i --){ 12 for(int j = i + 1; j <= len; j ++){ 13 String ss = s.substring(i,j); 14 if(dict.contains(ss) && j == len){ 15 map[i][j - 1] = true; 16 map[i][len] = true; 17 } 18 else if(dict.contains(ss) && j < len && map[j][len] == true){ 19 map[i][j - 1] = true; 20 map[i][len] = true; 21 } 22 } 23 } 24 if(map[0][len] != true) return al; 25 get(new StringBuffer(),0,s); 26 return al; 27 } 28 public void get(StringBuffer sb, int i,String s){ 29 if(i == len){ 30 String sa = sb.toString(); 31 al.add(sa.substring(0,sa.length() - 1)); 32 return; 33 } 34 if(map[i][len] == false) 35 return; 36 for(int j = i; j < len; j ++){ 37 if(map[i][j] == true){ 38 StringBuffer cur = new StringBuffer(); 39 cur.append(sb.toString()); 40 cur.append(s.substring(i,j + 1)); 41 cur.append(" "); 42 get(cur,j + 1,s); 43 } 44 } 45 } 46 }
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 }