public boolean wordBreak(String s, List<String> wordDict) {

int L = s.length();

if (L == 0) return true;

boolean[] dp = new boolean[L+1];

dp[0] = true;

int k = 0;

for (int i=0; i<=L; i++) {

for (int j=0; j<=i; j++) {

if (dp[j] && wordDict.contains(s.substring(j, i))) {

dp[i] = true;

}

}

}

return dp[L];

}

public boolean wordBreak2(String s, List<String> wordDict) {

boolean[] dp = new boolean[s.length()+1];

dp[0] = true;

for (int j=1; j<=s.length(); j++) {

for (String word: wordDict) {

if (j >= word.length() && s.startsWith(word, j - word.length()) && dp[j - word.length()]) dp[j] = true;

}

}

return dp[s.length()];

}