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

Solution:

This problem can be solve by using a naive approach, which is trivial. A discussion can always start from that though. Time: O(2^n).

首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔数组来存储信息。然后假设我们现在拥有res[0,...,i-1]的结果，我们来获得res[i]的表达式。思路是对于每个以i为结尾的子串，看看他是不是在字典里面以及他之前的元素对应的res[j]是不是true，如果都成立，那么res[i]为true，写成式子是

假设总共有n个字符串，并且字典是用HashSet来维护，那么总共需要n次迭代，每次迭代需要一个取子串的O(i)操作，然后检测i个子串，而检测是constant操作。所以总的时间复杂度是O(n^2)（i的累加仍然是n^2量级），而空间复杂度则是字符串的数量，即O(n)。

public class Solution {
    public boolean wordBreak(String s, Set dict) {
        if(s == null || s.length() == 0)
            return true;
        
        //Define res[] such that res[i]==true => 0-(i-1) can be segmented using dictionary
        boolean[] res = new boolean[s.length() + 1];
        res[0] = true;  //set first to be true, since we need initial state
        
        for(int i = 0; i < s.length(); i++) {
            StringBuilder str = new StringBuilder(s.substring(0, i+1));
            for(int j = 0; j <= i; j++) {
                if(res[j] == true && dict.contains(str.toString())) {
                    res[i + 1] = true;
                    break;
                }
                str.deleteCharAt(0);
            }
        }
        return res[s.length()];
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/22358863