package LeetCode;

import java.util.List;

public class LC_139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = false;
        }
        dp[0] = true;

        for (int i = 1; i <= dp.length; i++) {
            for (int j = 0; j < wordDict.size(); j++) {
                int len = wordDict.get(j).length();
                if (i >= len && wordDict.get(j).equals(s.substring(i - len, i)) && dp[i - len]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}