Word Break 107

Question

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Example

Given s = "lintcode", dict = ["lint", "code"].

Return true because "lintcode" can be break as "lint code".

Solution

wb[i]表示前i个字符能否组成dict中的word。在i之前寻找分割点j，若前j个字符的结果为true并且j－i的字符串在dict中，则wb[i]为true。

状态函数：wb[i] = wb[i-j] && dict.contains(s.substring(i-j, i))，j表示最后一个word的长度。即前i个字符能否组成dict中的word取决于前i-j个字符能否组成dict中的word以及最后一个字符串能否组成dict中的word。

其中，可以先遍历dict得到最长字符串的长度，然后将j限制在该长度内，可以优化时间。

代码如下：

public class Solution {
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    private int getMaxLength(Set<String> dict){
        int maxLength = 0;
        for(String curt : dict){
            if(curt.length() > maxLength){
                maxLength = curt.length();
            }
        }
        return maxLength;
    }
    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here
        if(s == null){
            return false;
        }

        int n = s.length();
        int maxLength = getMaxLength(dict);
        boolean[] wb = new boolean[n + 1];
        wb[0] = true;

        for(int i = 1; i <= n; i++){
            for(int lastLength = 1; lastLength <= maxLength && lastLength <= i; lastLength++){
                if(wb[i - lastLength]){
                    String last = s.substring(i - lastLength, i);
                    if(dict.contains(last)){
                        wb[i] = true;
                        break;
                    }
                }
            }
        }

        return wb[n];
    }
}