Trie

Trie

Index Pairs of a String

public int[][] indexPairs(String text, String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        insert(root, w);
    }

    List<int[]> list = new ArrayList<>();
    for (int i = 0; i < text.length(); i++) {
        TrieNode node = root;
        for (int j = i; j < text.length(); j++) {
            node = node.children[text.charAt(j) - 'a'];
            if (node == null) {
                break;
            }
            if (node.end) {
                list.add(new int[]{i, j});
            }
        }
    }

    int[][] result = new int[list.size()][2];
    for (int i = 0; i < result.length; i++) {
        result[i] = list.get(i);
    }
    return result;
}

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean end = false;
}

private void insert(TrieNode root, String word) {        
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        if (node.children[c - 'a'] == null) {
            node.children[c - 'a'] = new TrieNode();
        }
        node = node.children[c - 'a'];
    }
    node.end = true;
}

Prefix and Suffix Search

private TrieNode root = new TrieNode();

public WordFilter(String[] words) {
    for (int i = 0; i < words.length; i++) {
        String w = words[i];
        for (int j = w.length(); j >= 0; j--) {
            // '{' - 'a' == 27
            insert(root, w.substring(j) + "{" + w, i);
        }
    }
}

public int f(String prefix, String suffix) {
    String s = suffix + "{" + prefix;
    TrieNode node = root;
    for (char c : s.toCharArray()) {
        if (node.children[c - 'a'] == null) {
            return -1;
        }
        node = node.children[c - 'a'];
    }
    return node.index;
}

class TrieNode {
    TrieNode[] children;
    int index;  // index in the dictionary. Larger index overwrites the old one.

    TrieNode() {
        children = new TrieNode[27];
        index = 0;
    }
}

private void insert(TrieNode root, String word, int index) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        if (node.children[c - 'a'] == null) {
            node.children[c - 'a'] = new TrieNode();
        }
        node = node.children[c - 'a'];
        node.index = index;
    }
}

Implement Trie II (Prefix Tree)

class TrieNode {
    TrieNode[] children;
    int prefixCount;
    int wordCount;

    TrieNode() {
        children = new TrieNode[26];
        prefixCount = -1;
        wordCount = -1;
    }
}

Prefix Sum

Map Sum Pairs

// key : val
private Map<String, Integer> map = new HashMap<>();
private TrieNode root = new TrieNode();

/** Initialize your data structure here. */
public MapSum() {

}

public void insert(String key, int val) {
    int delta = val - map.getOrDefault(key, 0);
    map.put(key, val);

    TrieNode node = root;
    node.sum += delta;
    for (char c: key.toCharArray()) {
        node.children.putIfAbsent(c, new TrieNode());
        node = node.children.get(c);
        node.sum += delta;
    }
}

public int sum(String prefix) {
    TrieNode node = root;
    for (char c: prefix.toCharArray()) {
        node = node.children.get(c);
        if (node == null) {
            return 0;
        }
    }
    return node.sum;
}

class TrieNode {
    Map<Character, TrieNode> children;
    // sum of all the pairs' value whose key starts with the prefix
    // where prefix is from root to this node
    int sum;

    TrieNode() {
        children = new HashMap<>();
        sum = 0;
    }
}

Virtual Trie

K-th Smallest in Lexicographical Order

public int findKthNumber(int n, int k) {
    int curr = 1;
    while (k > 1) {
        // counts the nodes between the current node and its next node on the same level
        int count = countNodes(n, curr, curr + 1);
        if (count < k) {
            // moves to curr + 1
            curr++;
            k -= count;
        } else {
            // the k-th integer is in the subtree of current node
            // goes to the leftmost child node
            curr *= 10;
            k--;
        }
    }
    return curr;
}

// counts the nodes in [node1, node2)
// node1 and node2 are in the same subtree and on the same level
public int countNodes(int n, long node1, long node2) {
    int count = 0;
    while (node1 <= n) {
        // if node2 > n, n is in the range [node1, node2).
        //   adds (n - node1 + 1) to the count
        // else the subtree of node1 is complete.
        //   adds (node2 - node1) to the count
        count += Math.min(n + 1, node2) - node1;

        // next level
        node1 *= 10;
        node2 *= 10;
    }
    return count;
}

Traversal

Delete Duplicate Folders in System

private List<List<String>> ans = new ArrayList<>();

public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
    TrieNode root = new TrieNode();
    paths.forEach(p -> buildTree(root, p));

    deDupe(root);
    root.children.values().forEach(this::dfs);
    return ans;
}

class TrieNode {
    String name = null;
    // sorted map guarantees the serialization of identical subfolders is unique
    Map<String, TrieNode> children = new TreeMap<>();
    boolean toDelete = false;

    public TrieNode() {
    }

    public TrieNode(String name) {
        this.name = name;
    }
}

private void buildTree(TrieNode root, List<String> path) {
    for (String p : path) {
        root.children.putIfAbsent(p, new TrieNode(p));
        root = root.children.get(p);
    }
}

// backtracking
List<String> path = new ArrayList<>();
private void dfs(TrieNode root) {
    // skip deleted nodes
    if (root.toDelete) {
        return;
    }

    path.add(root.name);
    ans.add(new ArrayList<>(path));
    root.children.values().forEach(this::dfs);
    path.remove(path.size() - 1);
}

// postorder
Map<String, TrieNode> seen = new HashMap<>();
private String deDupe(TrieNode root) {
    String subfolders = "";

    for (TrieNode child : root.children.values()) {
        subfolders += deDupe(child);
    }

    if (!subfolders.isEmpty()) {
        if (seen.containsKey(subfolders)) {
            // if the subfolder has been seen before, marks the existing node as to-delete
            seen.get(subfolders).toDelete = root.toDelete = true;
        } else {
            seen.put(subfolders, root);
        }
    }

    // "()" ensures unique serialization
    return "("  + root.name + subfolders + ")";
}