Trie

208. Implement Trie (Prefix Tree)

Java

    /** Initialize your data structure here. */
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curt = root;
        for (char c : word.toCharArray()) {
            int id = c - 'a';
            if (curt.children[id] == null) curt.children[id] = new TrieNode();
            curt = curt.children[id];
        }
        curt.isWord = true;    
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return find(word.toCharArray(), root, false);
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return find(prefix.toCharArray(), root, true);
    }
    
    private boolean find(char[] chars, TrieNode curt, boolean prefix) {
        for (char c : chars) {
            int id = c - 'a';
            if (curt.children[id] == null) return false;
            curt = curt.children[id];
        }
        if (prefix) return true;
        return curt.isWord;
    }
    
    class TrieNode {
        TrieNode[] children;
        boolean isWord = false;
        TrieNode() {
            this.children = new TrieNode[26];
        }
    }

Python

211. Add and Search Word - Data structure design

Java

  class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean WordEnd;

    public TrieNode() {
      for (TrieNode node : children) {
        node = null;
      }
      WordEnd = false;
    }
  }

  /** Initialize your data structure here. */
  TrieNode root;
  public WordDictionary() {
    root = new TrieNode();
  }

  /** Adds a word into the data structure. */
  public void addWord(String word) {
    addWord(word, root);
  }

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

  /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
  public boolean search(String word) {
    return search(word.toCharArray(), 0, root);
  }

  private boolean search(char[] chars, int index, TrieNode curt) {
    if (index == chars.length) return curt.WordEnd;
    if (chars[index] == '.') {
        for (TrieNode child : curt.children) {
            if (child == null) continue;
            if (search(chars, index + 1, child)) return true;
        }  
    } else {
        if (curt.children[chars[index] - 'a'] == null) return false;
        return search(chars, index + 1, curt.children[chars[index] - 'a']);
    }
    return false;
  }

Python

1233. Remove Sub-Folders from the Filesystem

Build Trie and store index of the string in folder, the index has default value of -1.

BFS to find all parents, offer Tire root to the queue. While queue is not empty, pop nodes with index != -1, which means it is a parent folder. Check if it is children is not null and not 26 (which represent "/"), then it is another valid answer. For example, "/a/b/ca" is not a subfolder of "/a/b/c"

    class TrieNode {
        TrieNode[] children;
        int index;
        TrieNode() {
            children = new TrieNode[27];
            index = -1;
        }
    }
    
    TrieNode root;
    public List<String> removeSubfolders(String[] folder) {
        root = new TrieNode();
        for (int i = 0; i < folder.length; i++) {
            TrieNode curt = root;
            buildTrie(curt, folder[i], i);
        }
        List<String> result = new ArrayList<>();
        BFS(root, folder, result);
        return result;
    }
    
    private void BFS(TrieNode root, String[] folder, List<String> res) {
        Queue<TrieNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TrieNode curt = queue.poll();
            if (curt.index != -1) {
                res.add(folder[curt.index]);
            } 
            for (int i = 0; i < 27; i++) {
                if (curt.children[i] != null 
                    && !(i == 26 && curt.index != -1)) {
                    queue.offer(curt.children[i]);
                }
            }
        }
    }
    
    private void buildTrie(TrieNode curt, String s, int index) {
        for (char c : s.toCharArray()) {
            int id = c == '/' ? 26 : c - 'a';
            if (curt.children[id] == null) {
                curt.children[id] = new TrieNode();
            }
            curt = curt.children[id];
        }
        curt.index = index;
    }

212. Word Search II

When building Trie, add to the word to the end of Trie node. DFS search on Trie in 4 directions. Set the visited grid to '#' to eliminate revisit, flip it back as DFS completes.

T: O(m * n * 4 * 3 ^ (L - 1)) S : O(len*k)

    class TrieNode {
        TrieNode[] children;
        String word;
        TrieNode() {
            children = new TrieNode[26];
        }
    }

    TrieNode root = new TrieNode();
    public List<String> findWords(char[][] board, String[] words) {
        if (board == null || board.length == 0 || board[0].length == 0 || words.length == 0) {
            return new ArrayList<>();
        }
        for (String w: words) {
            buildTrie(w, root);
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }

    int[][] dirs = {{1,0}, {-1, 0}, {0,1}, {0,-1}};
    private void dfs(char[][] board, int x, int y, TrieNode curt, List<String> res) {
        if (!inbound(board, x, y) || board[x][y] == '#') return;
        int index = board[x][y] - 'a';
        curt = curt.children[index];
        if (curt == null) return;
        if (curt.word != null) {
            res.add(curt.word);
            curt.word = null;
        }
        char c = board[x][y];
        for (int[] d : dirs) {
            board[x][y] = '#';
            dfs(board, x + d[0], y + d[1], curt, res);
            board[x][y] = c; 
        }
    }

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

    private boolean inbound(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

1268. Search Suggestions System

Added 3 sorted suggestion words to the TrieNode. Traverse Trie by searchWord, add empty arrays if reached null nodes.

    TrieNode root;
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        root = new TrieNode();
        Arrays.sort(products);
        for (String product : products) {
            buildTrie(root, product);
        }
        List<List<String>> results = new ArrayList<>();
        char[] chars = searchWord.toCharArray();
        int i = 0; 
        while (i < chars.length) {
            int index = chars[i] - 'a';
            if (root.children[index] == null) {
                while (i++ < chars.length) {
                    results.add(new ArrayList<>());
                }
            } else {
                results.add(new ArrayList<>(root.children[index].words));
                root = root.children[index];
            }
            i++;
        }
        return results;
    }
    
    private void buildTrie(TrieNode curt, String w) {
        char[] arr = w.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i] - 'a';
            if (curt.children[index] == null) {
                curt.children[index] = new TrieNode();
            }
            curt = curt.children[index];
            if (curt.words.size() < 3) {
                curt.words.add(w);
            }
        }
        curt.isEnd = true;
    }
    
    class TrieNode {
        TrieNode[] children;
        List<String> words;
        boolean isEnd;
        TrieNode() {
            children = new TrieNode[26];
            words = new ArrayList<>();
        }
    }

472. Concatenated Words

Construct Trie Tree with words provided. When search, count the words which is already found and keep finding the next word from root, return true when total words find is >= 2.

T: build Trie: O(n * k) , search: O(n* k) S: O(n * k)

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<String>();
        if (words == null || words.length == 0) {
            return res;
        }
        TrieNode root = new TrieNode();
        for (String w : words) {
            addWord(w, root);
        }
        for (String w : words) {
            if (search(w.toCharArray(), 0, root, 0)) {
                res.add(w);
            }
        }
        return res;
    }

    public boolean search(char[] chars, int index, TrieNode root, int count) { 
        if (index == chars.length) return count >= 2;
        TrieNode curt = root;
        for (int i = index; i < chars.length; i++) {
            int id = chars[i] - 'a';
            if (curt.children[id] == null) return false;
            curt = curt.children[id];
            if (curt.isEnd && search(chars, i + 1, root, count + 1)) {
                return true;
            } 
        }
        return false;
    }

    public void addWord(String str, TrieNode root) {
        char[] chars = str.toCharArray();
        TrieNode cur = root;
        for (char c : chars) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur = cur.children[c - 'a'];
        }
        cur.isEnd = true;
    }

    class TrieNode {
        TrieNode[] children;
        boolean isEnd;
        public TrieNode() {
            children = new TrieNode[26];
        }
    }

212. Word Search II

Build Trie with words on the corresponding node. Simultaneously search the Trie and the board to find the word on the node, mark the grid as '#' to indicate visited, erase the word after added to the result. (this is because you only want to find one word if there are duplicates on the grid) Check if the x, y coordinates are out of bound or visited. Add word to the result.

T: O(M(4⋅3 L−1)), where MM is the number of cells in the board and LL is the maximum length of words.

    class TrieNode {
        TrieNode[] children;
        String word;
        TrieNode() {
            children = new TrieNode[26];
        }
    }

    TrieNode root = new TrieNode();
    public List<String> findWords(char[][] board, String[] words) {
        if (board == null || board.length == 0 || board[0].length == 0 || words.length == 0) {
            return new ArrayList<>();
        }
        for (String w: words) {
            buildTrie(w, root);
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }

    int[][] dirs = {{1,0}, {-1, 0}, {0,1}, {0,-1}};
    private void dfs(char[][] board, int x, int y, TrieNode curt, List<String> res) {
        if (!inbound(board, x, y) || board[x][y] == '#') return;
        int index = board[x][y] - 'a';
        if (curt.children[index] == null) return;
        curt = curt.children[index];
        if (curt.word != null) {
            res.add(curt.word);
            curt.word = null;
        }
        for (int[] dir : dirs) {
            char c = board[x][y];
            board[x][y] = '#';
            dfs(board, x + dir[0], y + dir[1], curt, res);
            board[x][y] = c;
        }
    }

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

    private boolean inbound(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

642. Design Search Autocomplete System

At each TrieNode, set children map and a separate map to count the corresponding word and frequency. Write a function List<String> getTop3() and use max heap to produce the top 3 words in each node.

AutocompleteSystem() takes O(k*l) time. We need to iterate over l sentences each of average length k, to create the trie for the given set of sentences. input() takes O(p+q+m *log m)time. Here, p refers to the length of the sentence

    TrieNode root;
    String prefix;
    public AutocompleteSystem(String[] sentences, int[] times) {
        root = new TrieNode();
        prefix = "";
        for (int i = 0; i < sentences.length; i++) {
            buildTrie(root, sentences[i], times[i]);
        }
    }

    private void buildTrie(TrieNode curt, String s, int time) {
        for (char c : s.toCharArray()) {
            TrieNode next = curt.children.get(c);
            if (next == null) {
                next = new TrieNode();
                curt.children.put(c, next);
            }
            curt = next;
            curt.count.put(s, curt.count.getOrDefault(s, 0) + time);
        }
        curt.isEnd = true;
    }

    public List<String> input(char c) {
        if (c == '#') { // add prefix to Trie and reset prefix
            buildTrie(root, prefix, 1);
            prefix = "";
            return new ArrayList<>();
        }
        prefix = prefix + c;
        TrieNode curt = root;
        for (char cc: prefix.toCharArray()) {
            if (curt.children.get(cc) == null) return new ArrayList<>();
            curt = curt.children.get(cc);
        }
        return curt.getTop3();
    }

    class TrieNode {
        Map<Character, TrieNode> children;
        Map<String, Integer> count;
        boolean isEnd;
        TrieNode() {
            this.children = new HashMap<>();
            this.count = new HashMap<>();
            this.isEnd = false;
        }
        
        public List<String> getTop3() {
            List<String> res = new ArrayList<>();
            PriorityQueue<Map.Entry<String, Integer>> pq
                    = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                    if (o1.getValue() == o2.getValue()) {
                        return o1.getKey().compareTo(o2.getKey());
                    }
                    return o2.getValue() - o1.getValue();
                }
            });

            pq.addAll(count.entrySet());
            for (int i = 0; i < 3 && !pq.isEmpty(); i++) {
                res.add(pq.poll().getKey());
            }
            return res;
        }
    }

1032. Stream of Characters

TrieNode root;
StringBuilder sb;
public StreamChecker(String[] words) {
    root = new TrieNode();
    for (String w : words) {
        add(w.toCharArray());
    }
    sb = new StringBuilder();
}

public boolean query(char letter) {
    sb.append(letter);
    TrieNode curt = root;
    for (int i = sb.length() - 1; i >= 0; i--) {
        int index = sb.charAt(i) - 'a';
        if (curt.children[index] == null) return false;
        curt = curt.children[index];
        if (curt != null && curt.isWord) return true;
    }
    return false;
}

class TrieNode {
    TrieNode[] children;
    boolean isWord;
    TrieNode() {
        children = new TrieNode[26];
        isWord = false;
    }
}

private void add(char[] chars) {
    TrieNode curt = root;
    for (int i = chars.length - 1; i >= 0; i--) {
        int id = chars[i] - 'a';
        if (curt.children[id] == null) curt.children[id] = new TrieNode();
        curt = curt.children[id];
    }
    curt.isWord = true;
}

792. Number of Matching Subsequences

Solution1: Build & Search all words in Trie (Build: O(L), Search (n * L * 26))

Solution2: Rolling Character Matching (O(S + W * L))

Solution1

public int numMatchingSubseq(String S, String[] words) {
    TrieNode root = new TrieNode();
    buildTrie(S, root);
    int count = 0;
    Map<String, Integer> map = new HashMap<>();
    for (String w : words) {
        map.put(w, map.getOrDefault(w, 0) + 1);
    }
    for (String w : map.keySet()) {
        if (dfs(root, w.toCharArray(), 0)) {
            count += map.get(w);
        }
    }
    return count;
}

private boolean dfs(TrieNode curt, char[] chars, int i) {
    if (i == chars.length) {
        return true;
    }
    int index = chars[i] - 'a';
    if (curt.children[index] != null) {
        return dfs(curt.children[index], chars, i + 1);
    } else {
        for (int k = 0; k < 26; k++) {
            if (curt.children[k] != null && dfs(curt.children[k], chars, i)) {
                return true;
            }
        }
    }
    return false;
}

private void buildTrie(String s, TrieNode curt) {
    for (int i = 0; i < s.length(); i++) {
        int index = s.charAt(i) - 'a';
        if (curt.children[index] == null) {
            curt.children[index] = new TrieNode();
        }
        curt = curt.children[index];
    }
    curt.isEnd = true;
}

class TrieNode {
    TrieNode[] children;
    boolean isEnd;
    TrieNode() {
        children = new TrieNode[26];
    }
}

Solution2

527. Word Abbreviation