Problem

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

Note

基础动规题目，有几个细节要注意。dp[0]是指，当s为空的时候的word-dict映射布尔值；另外，循环s第i个字符的时候，若该位已经判断过没有映射在dict中的word，就跳过；若这一位开始，加上从dict中取词的长度越界，则跳过；若dict中的取词和这一位起始的子字符串相等，则给子字符串的最后一个字符映射的dp[j]赋true。

Solution

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 = 0; i < n; i++) {
            if (!dp[i]) continue;
            for (String word: dict) {
                int l = word.length(), j = i + l;
                if (j > n || dp[j]) continue;
                if (word.equals(s.substring(i, j))) dp[j] = true;
            }
        }
        return dp[n];
    }
}