1
class Solution {
2
  Map<String, Boolean> map = new HashMap<>();
3

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

6
    if (wordDict.contains(s)) {
7
      return true;
8
    }
9
    if (map.containsKey(s)) {
10
      return map.get(s);
11
    }
12
    for (int i = 0; i < s.length(); ++i) {
13
      String left = s.substring(0, i);
14
      if (wordDict.contains(left) && wordBreak(s.substring(i), wordDict)) {
15
        map.put(s, true);
16
        return true;
17
      }
18
    }
19
    map.put(s, false);
20
    return false;
21
  }
22
}