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

    if (s.length() == 0) {
      return true;
    }

    // DFS
    LinkedList<String> stack = new LinkedList<String>();
    stack.push(s);

    while (!stack.isEmpty()) {

      String currt = stack.pop();

      for (int i = 1 ; i <= currt.length() ; i++) {
        String leftStr = currt.substring(0, i);
        String rightStr = currt.substring(i);
        if (dict.contains(leftStr)) {
          if (rightStr.isEmpty()) {
            return true;
          } else {
            stack.push(rightStr);
          }
        }
      }
    }

    return false;
  }