# 2ms Java solution, DP. Bonus ugly streams solution :)

• Counting the max string length in the dictionary and terminating the inner loop early speeds it up from 9ms to 2ms.

``````public boolean wordBreak(String s, Set<String> wordDict) {
int[] mem = new int[s.length()+1];
mem[0] = 1;
int max = 0;
for (String word: wordDict)
max = Math.max(max,word.length());
for (int i = 0; i < s.length(); i++)
if (mem[i] == 1)
for (int j = i; j < mem.length && j - i <= max; j++)
if (wordDict.contains(s.substring(i,j)))
mem[j] = 1;
return mem[s.length()] == 1;
}
``````

Ugly bonus:

``````public boolean wordBreak(String s, Set<String> wordDict) {
if (wordDict.size() == 0) return false;
short[] mem = new short[s.length()+1];
mem[0] = 1;
IntStream.range(0, s.length())
.forEach(i -> {
if (mem[i] == 1)
IntStream.range(i, s.length() + 1)
.filter(j -> wordDict.contains(s.substring(i,j)))
.forEach(j -> mem[j] = 1);
});
return mem[s.length()] == 1;
}``````

• `int max` is not used in the streams version...

• This post is deleted!

• Two premature? optimizations for the inner loop:

1. Simplify loop condition, calculate range only once (it hurts readability a bit):

``````for (int j = Math.min(i + max, s.length()); j > i; --j)
``````
2. Skip processing if we already have a solution: we may find an alternative at best, so we can save a `substring` (linear time) and a `contains` (amortized constant or log time [don't know if it's a HashSet we receive]).

``````if (mem[j] == 1) continue;
``````

Neither decreased the 2ms runtime though, but I think it's because the inputs are too small.

• Thanks for noticing. Removed.

1. Yes, this does indeed save one comparison per loop cycle.
2. I tried this before and, since it didn't improve the runtime, decided to remove it to keep the code shorter and avoid, as you said, premature optimizing if's.
• Just one more little thing: you start at `j = i` which means `s.substring(i,i).equals("")`. We already know that `mem[j] == mem[i] == 1` so checking is superfluous like in 2., therefore starting at `j = i + 1` is equivalent.