Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

[解题思路]

1.brute force will TLE.

just check every substring from index 0 to the end.

1 public boolean wordBreak(String s, Set
     
       dict) { 2         // Note: The Solution object is instantiated only once and is reused by each test case. 3         int len = s.length(); 4         boolean flag = false; 5                6         for(int i = 1; i <= len; i++){ 7             String subStr = s.substring(0, i); 8             if(dict.contains(subStr)){ 9                 if(subStr.length() == s.length()){10                     return true;11                 }   12                 flag = wordBreak(s.substring(i), dict);13             }14         }15         return flag;16     }
     

 

2.DP

Reference the dicussion in leetcode.

Here we use seg(i, j) to demonstrate whether substring start from i and length is j is in dict?

base case:

when j = 0; seg(i, j) = false;

State transform equation:

seg(i, j) = true. if s.substring(i, j - 1) is in dict.

else seg(i, j) = seg(i, k) && seg(i + k, j - k);

1 public boolean wordBreak(String s, Set
     
       dict) { 2         // Note: The Solution object is instantiated only once and is reused by each test case. 3         if(s == null || dict.size() <= 0){ 4             return false; 5         } 6          7         int length = s.length(); 8         // seg(i, j) means substring t start from i and length is j can be segmented into  9         // dictionary words10         boolean[][] seg = new boolean[length][length + 1];11         for(int len = 1; len <= length; len++){12             for(int i = 0; i < length; i++){13                 String t = s.substring(i, i + len);14                 if(dict.contains(t)){15                     seg[i][len] = true;16                     continue;17                 }18                 for(int k = 1; k < len; k++){19                     if(seg[i][k] && seg[i+k][len-k]){20                         seg[i][len] = true;21                         break;22                     }23                 }24             }25         }26         return seg[0][length];27     }
     

 

这题貌似是一道面试题：