leetcode--11. 动态规划 I

题目：
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".
给定字符串s和单词字典，确定s是否可以分割成一个或多个字典单词的空格分隔序列。
例如，给定s=“leetcode”，dict=[“leet”，“code”]。返回true，因为“leetcode”可以分割为“leet code”。

思路：
动态规划，比如leet存在字典中可切，则后面可以从第5位往后判断

import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for(int i = 1; i <= len; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && dict.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}