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

    if (s.isEmpty()) {
      return true;
    }

    boolean flag = false;

    for (int i = 1 ; i <= s.length() ; i++) {

      String prefix = s.substring(0, i);

      if (dict.contains(prefix)) {

        String suffix = s.substring(i);

        if (cache.contains(suffix)) {
          continue;
        } else {
          flag = wordBreakPrune(suffix, dict);

          if (flag) {
            return true;
          } else {
            cache.add(suffix);
          }
        }
      }
    }

    return false;
  }