# java solution beats 94.18%

• ``````public static boolean wordBreak(String s, List<String> wordDict) {
/**
*  dp[i] means if the string before i(not the index,it start from 1) th character in s
*  can break into words.
*/
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < wordDict.size(); j++) {
String word = wordDict.get(j);
int len = word.length();
/**
* every time we meet a word in dictionary, we judge if
* the string before (i+1-len) can break,if it can not be
* break,there is no need to go along,otherwise,then,
* we judge if the string between(i+1-len) and i equals
* the current word in dictionary
*
* for example, given s="leetcode" and dictionary ["leet","code"]
* we iterate i from 0 to s.length-1,here from 0 to 7
* since character before t, the length is no more than
* any word in dictionary,so we just ignore,and the dp[1]-dp[3] will
* be set to false.when i arrive 3,here it means arrive to the
* character 't',we judge dp[i + 1 - len] = dp[3+1-4] = dp[0](this is why we
* initially set dp[0] = true),since dp[0] = true,we come to substring string
* between (i + 1 -len) and i ,since substring method does not include the end,
* we substring from(i+1-len,i+1) here s.substring(0,4) = "leet",it equals
* the first string in dictionary.so we find it and break the inner loop,
* so we set dp[i+1] = dp[3+1] = dp[4] = true, it means string before the 4th
* character (inclusive)in s can break into words.
*/
if (len <= (i+1) && dp[i+1-len]) {
if (s.substring(i + 1 - len,i + 1).equals(word)) {
dp[i + 1] = true;
break;
}
}
}
}
return dp[s.length()];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.