class Solution {
    //动态规划 dp[]代表前i个字符能否由List里的字符串组成
    //初始化dp[0] = 0;
    //遍历顺序：从左到右
    //递推公式 
    //s.substring(start,endIndex) start是起始索引，endIndex是结束索引，不包括
    // 排列而不是组合
    public boolean wordBreak(String s, List<String> wordDict) {
            int n = s.length(); 
            boolean[] dp = new boolean[s.length() + 1];  //代表s的前i个元素能否由字典中的元素组成
            dp[0] = true;
            for (int i = 1; i <= n; i++) {
                for (String str : wordDict) {
                    if (i >= str.length() && dp [i - str.length()] && s.substring(i - str.length(), i).equals(str)) {
                        dp[i] = true;
                    }
                }
            } 
            return dp[n];
    }
}