[LeetCode每日一题]139. Word Break

题目如下：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

139. Word Break
给定一个字符串s和一个字典wordDict，判断s是否可以由字典中的词组成。
这道题可以用动态规划解决，设dp[i]表示长度为i的字符是否满足条件，求解该值需要进行一层循环，变量j从1递增到max(i,最长单词的长度)，dp[i]为真的条件是dp[j]==true&&s.subString(i-j，j)在字典中。
实现代码如下：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
        dp[0] = true;
        Set<String> dict = new HashSet<>();
        dict.addAll(wordDict);
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= i && j <= maxLen; j++) {
                if (dp[i - j] && dict.contains(s.substring(i-j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}