Word Break

题目：

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

这题拿到就开始硬做。。是不对滴。用DP做怎样？搞清楚state，function，initialize和result。

 1 public boolean wordBreak(String s, Set<String> dict) {
 2         int maxWordLen = 0;
 3         for (String str : dict) {
 4             maxWordLen = Math.max(maxWordLen, str.length());
 5         }
 6         //F[i] 代表在i时，前面的是否可以被字典中的词拆分
 7         //F[i] = (F[j] && dict.contains(s.substring(j ,i)))
 8         //F[0] = true;
 9         //return F[s.length()]
10         boolean[] F = new boolean[s.length() + 1];
11         F[0] = true;
12         for (int i = 1; i <= s.length(); i++) {
13             F[i] = false;
14             for (int j = 0; j < i && j <= maxWordLen; j++) {
15                 if (F[i - j - 1] && dict.contains(s.substring(i - j - 1, i))){
16                     F[i] = true;
17                 }
18             }
19         }
20         return F[s.length()];
21     }