Digraph With Adjacency List

Inspired by Digraph (Algorithms 4/e) – Algorithms, 4th Edition

Digraph.java

//Digraph implementation with adjacency list
public class Digraph<V>{

    private Map<V,List<DirectedEdge<V>>> vertexes;

    private int eCount;

    public Digraph(){
        this.vertexes = new HashMap<>();
    }

    public int V(){
        return vertexes.size();
    }

    public int E(){
        return eCount;
    }

    public List<DirectedEdge<V>> adj(V vertex){
        return vertexes.get(vertex);
    }

    public void addEdge(DirectedEdge<V> de){
        if (de == null){
            return;
        }
        if (!vertexes.containsKey(de.from())){
            vertexes.put(de.from(), new ArrayList<>());
        }
        if (!vertexes.containsKey(de.to())){
            vertexes.put(de.to(), new ArrayList<>());
        }
        vertexes.get(de.from()).add(de);
        ++eCount;
    }

    //O(V+E)
    public List<DirectedEdge<V>> getEdges(){
        List<DirectedEdge<V>> res = new ArrayList<DirectedEdge<V>>(eCount);
        for (V v : vertexes.keySet()){
            res.addAll(vertexes.get(v));
        }
        return res;
    }

    public Set<V> getVertexes(){
        return vertexes.keySet();
    }
}

DirectedEdge.java

public class DirectedEdge<V>{

    private V from;
    private V to;

    public DirectedEdge(V from, V to){
        this.from = from;
        this.to = to;
    }

    public V from(){
        return from;
    }

    public V to(){
        return to;
    }

    @Override
    public String toString(){
        return from.toString() + "-->" + to.toString();
    }

}

Trie

Trie, or prefix tree, is a search tree that stores associative arrays or dynamically resizable collections per node. From every regular node one can search a value by key (key defines position of node with corresponding value in collection). Nodes on every path starting from level 0 (direct children of root) share the common prefix. Path from level 0 to terminal node represents a complete word (for example, ‘MAP’).

One can search a word in trie in O(M) time, where M is length of word to be searched. In case of word miss, search will terminate on some node along the path and return faster than in O(M) (depends on concrete structure of trie). Insertions and deletions will perform at worst in O(M).
trie2
Java

Time complexity: O(M) for search, insert and delete, M – length of word

Space complexity: O(N*26) -> O(N), per every node we store constant number of references to child nodes, bounded by size of alphabet


class TrieNode {

        public static final int R = 26;//size of alphabet

        private TrieNode[] next = new TrieNode[R];

        private boolean isTerminal;

        // Initialize your data structure here.
        public TrieNode() {

        }
        public void setTerminal(){
            this.isTerminal = true;
        }

        public boolean isTerminal(){
            return isTerminal;
        }

        public TrieNode setNext(int c){
            int k = c - 'a';
            if (next[k] != null){
                return next[k];
            } else {
                TrieNode newNode = new TrieNode();
                next[k] = newNode;
                return newNode;
            }
        }

        public TrieNode getNext(char c){            
            return next[c - 'a'];
        }
}

public class Trie {
        private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode curr = root;
        for (Character c : word.toCharArray()){
            curr = curr.setNext(c);
        }
        curr.setTerminal();
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode curr = root;
        for (Character c : word.toCharArray()){
            curr = curr.getNext(c);
            if (curr == null){
                return false;
            }
        }
        return curr.isTerminal();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (Character c : prefix.toCharArray()){
            curr = curr.getNext(c);
            if (curr == null){
                return false;
            }
        }
        return true;
    }
}