Slightly hamfisted digraph solution (Accepted, Java)

• ``````public class Solution {

public List<String> wordBreak(String s, Set<String> dict) {
DirectedGraph<Integer, Boolean> digraph = constructWordBreakGraph(s, dict);

return mapTerminalPathsToStrings(digraph, s);
}

private DirectedGraph<Integer, Boolean> constructWordBreakGraph(String s,
Set<String> dict) {

DirectedGraph<Integer, Boolean> digraph = new DirectedGraph<>();
Set<Integer> unvisited = new HashSet<>();

while (!unvisited.isEmpty()) {
// "Remove first" from a set is awkward as hell
Iterator<Integer> node = unvisited.iterator();
int idx = node.next();
node.remove();

if (idx >= s.length()) {
continue;
}

for (String word : dict) {
if (inplaceStartsWith(idx, word, s)) {
}
}
}

return digraph;
}

private List<String> mapTerminalPathsToStrings(
DirectedGraph<Integer, Boolean> digraph, String s) {

Map<Integer, Set<String>> subStrings = new HashMap<>();

while (!unvisited.isEmpty()) {
int endIdx = unvisited.poll();

Set<Integer> incomingEdges = digraph.getIncomingEdges(endIdx);

for (Integer startIdx : incomingEdges) {
String substr = s.substring(startIdx, endIdx);
for (String suffix : subStrings.get(endIdx)) {
}
}
}

return new ArrayList<>(subStrings.getOrDefault(0,  Collections.emptySet()));
}

private String combineStrings(String prefix, String suffix) {
if (suffix.isEmpty()) {
return prefix;
}
else {
return prefix + " " + suffix;
}
}
boolean inplaceStartsWith(int idx, String prefix, String str) {
final int length = Math.min(prefix.length(), str.length() - idx);
for (int i = 0; i < length; i++) {
if (str.charAt(i+idx) != prefix.charAt(i)) {
return false;
}
}
return true;
}

static class DirectedGraph<N, V> {
private final Map<N, V> values;
private final Map<N, Set<N>> edgesTo;
private final Map<N, Set<N>> edgesFrom;

public DirectedGraph() {
values = new HashMap<>();
edgesTo = new HashMap<>();
edgesFrom = new HashMap<>();
}

public DirectedGraph(DirectedGraph<N, V> other) {
values = new HashMap<>(other.values);
edgesTo = new HashMap<>(other.edgesTo);
edgesFrom = new HashMap<>(other.edgesFrom);
}

public Set<N> nodes() {
Set<N> nodes = new HashSet<>();

return nodes;
}

public void addEdge(N source, N dest) {
edgesTo.computeIfAbsent(source,
edgesFrom.computeIfAbsent(dest,
}

public void removeEdge(N source, N dest) {
boolean removed = edgesTo.computeIfAbsent(source,
(n) -> new HashSet<>()).remove(dest);
removed = removed & edgesFrom.computeIfAbsent(dest,
(n) -> new HashSet<>()).remove(source);

if (!removed) {
// handle error state perhaps? IllegalStateException, I don't know...
}
}

public void removeNode(N node) {
values.remove(node);
edgesTo.remove(node);
edgesFrom.forEach((source, edges) -> edges.remove(node));
}

public Set<N> getIncomingEdges(N node) {
final Set<N> edgesPointingToNode = edgesFrom.getOrDefault(node, Collections.emptySet());
return new HashSet<>(edgesPointingToNode);
}

public int countIncomingEdges(N node) {
return edgesFrom.getOrDefault(node, Collections.emptySet()).size();
}

public Set<N> getOutgoingEdges(N node) {
final Set<N> edgesFromNode = edgesTo.getOrDefault(node, Collections.emptySet());
return new HashSet<>(edgesFromNode);
}

public Set<N> getNeighbors(N node) {

final Set<N> edgesPointingToNode = edgesFrom.getOrDefault(node, Collections.emptySet());
final Set<N> edgesFromNode = edgesTo.getOrDefault(node, Collections.emptySet());

if (edgesPointingToNode.isEmpty() && edgesFromNode.isEmpty()) {
return Collections.emptySet();
}

final Set<N> returnSet = new HashSet<>();