题目， 反正就是一个string，要不自己在字典里，要不切几刀，切出来的每个词都在字典里

———————————————————————————————————————————————————————-

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

———————————————————————————————————————————————————————-

最笨的解法，DFS

public class Solution {    public boolean wordBreak(String s, Set<String> dict) {        // IMPORTANT: Please reset any member data you declared, as        // the same Solution instance will be reused for each test case.        if (dict.contains(s)) return true;        if (s==null || s.length()==0) return false;        return helper(s, 0, dict);    }    public boolean helper(String s, int i, Set<String> dict) {        int n = s.length();        if (i>=n) return false;        int j = i;        while (j<n) {            while(j<n && !dict.contains(s.substring(i,j+1))) {                j++;            }            if (j==n) return false;            boolean goodAfter = helper(s, j+1, dict);            if (goodAfter) return true;            j++;        }        return false;    }}

我不确定对： 没有额外空间，空间O(1)。每次recursion，都要loop O(n), 时间O(n^n)

毫无意外是会超时的，要加速基本要上DP了。关键是DP记录什么东西不好想，反正我是想了很久都没想到。最后看了大牛的答案才明白。还是bottom up approach。比如String长度为0，问题成立吗？ 然后String长度为1，成立吗? 一直到n。所以dp就是记录从头开始的substring的长度和问题能否成立的关系。关键是dp[i]怎样可以利用dp[k], k=0,.., i-1的结果？就要在找0到i-1中找到一个k，使得dp[k] && dict.contains(s.substring(k, i))为真。意义是从0到k-1之间的substring，已经有办法用字典的词组成了，而且如果k到i-1之间的substring也在字典里，那么从0开始，长度为i的string就可以由字典里的词组成。

注意的是dp[0] == true是因为如果整个词都在字典里，那么就可以由字典的词组成。

优化解法：一维DP

public class Solution {    public boolean wordBreak(String s, Set<String> dict) {        int n = s.length();        boolean[] dp = new boolean[n+1];        dp[0] = true;        for (int i=1; i<=n; i++) {            for (int j=0; j<i; j++) {                if (dp[j] && dict.contains(s.substring(j,i))) {                    dp[i] = true;                    break;                }            }        }        return dp[n];    }}

空间 O(n), 时间O(n^2)

这种方法好像在leetcode很常见，以后要总结一下。

http://stupidcodergoodluck.wordpress.com/2013/11/15/leetcode-word-break/

leetcode-word break