LeetCode OJ - Word Break

 1 /**
 2      * Word break
 3      * Given a string s and a dictionary of words dict, 
 4      * determine if s can be segmented into a space-separated sequence of one or more dictionary words.
 5      * 采用动态规划算法；设数组Db[0...len], Db[i]表示string[0...i]是可segmented的
 6      * 采用动态规划时，很关键的一点是得弄清楚子问题是什么。    
 7      * 当我在考虑第i个字符时，我应该是从前面的Db[j]为true的j+1开始到i，这段字串是否在dict中，如果不再，则继续往前找合适的j（这里的合适指的是Db[j]为true）
 8      * @param s
 9      * @param dict
10      * @return
11      */
12     public boolean wordBreak(String s, Set<String> dict)
13     {
14         //if the dict is empty, return false
15         if(dict.size()<=0)
16             return false;
17         boolean[] Db = new boolean[s.length()];
18         //initialize
19         if(dict.contains(s.substring(0,1)))
20             Db[0] = true;
21         else
22             Db[0] = false;
23         //DP process
24         for(int i=1;i<s.length();i++)
25         {
26             Db[i] = false;
27             int j = i-1;
28             while(j>=0)
29             {
30                 if(Db[j] && dict.contains(s.substring(j+1,i+1)))
31                 {
32                     Db[i] = true;
33                     break;
34                 }
35                 j--;        
36             }
37             if(!Db[i] && j<0 && dict.contains(s.substring(0,i+1)))
38                 Db[i] = true;
39                 
40                 
41         }
42         return Db[s.length()-1];
43     }