public boolean wordBreak(String s, Set<String> dict) {

    // dp[i] means sub string 0 to i can be broken
    boolean[] dp = new boolean[s.length()];

    for (int i = 0 ; i < s.length() ; i++) {
      if (dict.contains(s.substring(0, i + 1))) {
        dp[i] = true;
      }
    }

    for (int i = 1 ; i < s.length() ; i++) {
      for (int j = 0 ; j < i ; j++) {
        if (dp[j] && dict.contains(s.substring(j + 1, i + 1))) {
          dp[i] = true;
          break;
        }
      }
    }

    return dp[s.length() - 1];
  }