Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

Given s ="lintcode", dict =["lint", "code"].

Return true because"lintcode"can be break as"lint code".

Solution: dp[i]:前i个字符能否break，dp[i] = true if (dp[i - j] && hashset.contains(input.substring(i - j, i)))

为了把O(n^3)变为O（n^2*l), 设置循环长度为字典里最长的词的长度

  public boolean canBreak(String input, String[] dict) {
    Set<String> hashset = new HashSet<>();
    int max = 0;
    for (String cur : dict) {
      hashset.add(cur);
      max = Math.max(max, cur.length());
    }
    boolean[] dp = new boolean[input.length() + 1];
    dp[0] = true;
    for (int i = 1; i < dp.length; i++) {
      for (int j = 1; j <= i && j <= max; j++) {
        if (dp[i - j] == false) {
          continue;
        }
        if (hashset.contains(input.substring(i - j, i))) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[input.length()];
  }