Slightly hamfisted digraph solution (Accepted, Java)


  • 1
    V
    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<>();
            unvisited.add(0);
    
    		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)) {
    					digraph.addEdge(idx, idx + word.length());
    					unvisited.add(idx + word.length());
    				}
    			}
    		}
    
    		return digraph;
    	}
    
    	private List<String> mapTerminalPathsToStrings(
    			DirectedGraph<Integer, Boolean> digraph, String s) {
    
    		Map<Integer, Set<String>> subStrings = new HashMap<>();
    		LinkedList<Integer> unvisited = new LinkedList<>();
    
    		unvisited.add(s.length());
    		subStrings.computeIfAbsent(s.length(), (key)->new HashSet<>()).add("");
    
    		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)) {
    					subStrings.computeIfAbsent(startIdx, (key)->new HashSet<>()).add(combineStrings(substr, suffix));
    				}
    				unvisited.add(startIdx);
    			}
    		}
    
    		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<>();
        		
        		nodes.addAll(values.keySet());
        		nodes.addAll(edgesTo.keySet());
        		nodes.addAll(edgesFrom.keySet());
        		
        		return nodes;
        	}
        
        	
        	public void addEdge(N source, N dest) {
        		edgesTo.computeIfAbsent(source, 
        				(n) -> new HashSet<>()).add(dest);
        		edgesFrom.computeIfAbsent(dest, 
        				(n) -> new HashSet<>()).add(source);
        	}
        	
        	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<>();
        		returnSet.addAll(edgesFromNode);
        		returnSet.addAll(edgesPointingToNode);
        		
        		return returnSet;
        
        	}
        }
        	
    	
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.