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

/* 
 *  “leetleet” ["leet", "code"] return true
 */

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s == null||dict.isEmpty())
            return false;
        int length = s.length();
        boolean[][] seg = new boolean[length][length + 1];
        for(int len = 1; len <= length; len++){
            for(int i = 0; i < length; i++){
                int tmp = i + len;
                if(i+len > length)
                        tmp = length;
                String t = s.substring(i, tmp);
                if(dict.contains(t)){
                    seg[i][len] = true;
                    continue;
                }
                for(int k = 1; k < len; k++){
                    if(seg[i][k] && seg[i+k][len-k]){
                        seg[i][len] = true;
                        break;
                    }
                }
            }
        }
        return seg[0][length];
        
    }
}

 ref: http://www.cnblogs.com/feiling/p/3357022.html

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        int len = s.length();
        for(int i = 0; i< len; i++){
            if(!dp[i])
                continue;
            for(String e : dict){
               // end 为 dict 中的单词长度在substring终止时的下标
                int end = i+e.length();
                if(end > s.length())
                    continue;
                String sub = s.substring(i, end);
                if(dict.contains(sub))
                    dp[end] = true;
            }
        }
         return dp[len];
    }
   
}

Ref ： 水中的鱼 + word break

[Thoughts]

一个DP问题。定义possible[i] 为S字符串上[0,i]的子串是否可以被segmented by dictionary.

那么

possible[i] = true      if  S[0,i]在dictionary里面

                = true      if   possible[k] == true 并且 S[k+1,j]在dictionary里面， 0<k<i

               = false      if    no such k exist.

[Code]

实现时前面加一个dummy节点，这样可以把三种情况统一到一个表达式里面。

我不确定对： 没有额外空间，空间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)