public class Solution {
  public boolean canBreak(String input, String[] dict) {
    Set<String> dictSet = new HashSet<>();
    for (String s : dict) {
      dictSet.add(s);
    }
    boolean[] canBreak = new boolean[input.length() + 1];
    canBreak[0] = true;
    for (int i = 1; i <= input.length(); i++) {
      for (int j = 0; j < i; j++) {
        if (dictSet.contains(input.substring(j, i)) && canBreak[j]) {
          canBreak[i] = true;
        }
      }
    }
    return canBreak[input.length()];
  }
}

High Level：

detail：用一个Set<String>存 dict

TC: O(n^3); substring API时间复杂度是O(n), hashSet.contains时间复杂度是O(1), 总共

SC: O(n)