Trie 字典树

Posted on by oneOokay

应用

  • 查询包含某个前缀的单词/字符串是否存在
  • 字符矩阵中找单词
  • Time Complexity: O(L) L: word length -> add/delete/search/find/update
  • Space Complexity: O(N * L) N: word count; L: word length

Trie Implementation

主要看TrieNode

  • Map<Character, TrieNode> children -> 代表从这个TrieNode往下连接的chars, 每一个char有他相应的TrieNode
  • isWord: 表示从root到现在这个TrieNode是否是一个word
  • word: 表示从root到现在这个TrieNode所组成的word
class Trie {
        class TrieNode {
        public Map<Character, TrieNode> children;
        public boolean isWord;
        public String word;
        public TrieNode() {
            isWord = false;
            word = "";
            children = new HashMap<>();
        }
    }
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode n = root;
        for(char c : word.toCharArray()) {
            n.children.putIfAbsent(c, new TrieNode());
            n = n.children.get(c);
        }
        n.isWord = true;
        n.word = word;
    }
    public boolean search(String word) {
        TrieNode n = root;
        for(char c : word.toCharArray()) {
            if (!n.children.containsKey(c)) return false;
            n = n.children.get(c);
        }
        return n.isWord;
    }
    public boolean startsWith(String prefix) {
        TrieNode n = root;
        for(char c : prefix.toCharArray()) {
            if (!n.children.containsKey(c)) return false;
            n = n.children.get(c);
        }
        return true;
    }
}

Trie & DFS

  • 一定一定要注意传入的trieNode是一个parent node还是curNode
    • root是一个parent node
    • 对应第一个char c的node其实是root.children.get(c)
    • 似乎可以统一都先传入parent node, 之后再通过parent node来取得curNode, 之后再看情况要不要直接update成curNode
  • 灵活应用TrieNode.isWord/ TrieNode.word
    • 当找到一次word之后, reset这两个flag可以避免这个词再被找到 => 212. Word Search II
    • 同时可以进行remove => 212. Word Search II

212. Word Search II

  • 因为这个题目是需要在board上面一个char一个char的寻找看是否能够构成一个word, 所以用trie比较合适
    • trieNode.children.containsKey(char) 决定是否可以从当前位置上下走动
    • trieNode.word / trieNode.isWord 来确定当前是否一个valid word
      • NOTE:
        • 到当前的char时, trieNode是一个word的话, 把word加入res中, 不能return, 而应该继续往下寻找. 因为可能存在单词A是单词B的prefix的情况
        • 当找到一个word, trieNode是一个word的话, 可以把这个trieNode的word的标识给消掉, 这样可以避免在res里面加入重复的单词 => 这个可以减少很多的时间复杂度
  • 给Trie剪枝
    • when? 在dfs的最后backtracking的时候: 即 remove cur from path的时候
    • how ? 如果curNode.children为0的话, 就可以把这个curNode从它的parent里面移除
      1. curNode.children为0说明这个node是一个单词的最后一个trieNode且它之后没有任何词
      2. 题目里面不需要返回找到的单词的次数, 每个词只需要找到一次就好
      3. 在backtracking的到了最后一个单词的char, 说明这个单词已经找完了, 不需要他了, 所以可以把他删掉
      4. 怎么删? 从这个curNode的parent里面把它删掉 => 所以这里dfs里面应该要传入一个parent node, 而不是传入curNode
    • 最终如果在board里面找齐了trie里面的所有的word, trie就会变成一个空的trie.
  • dfs
    • 需要对board上的每一个char都进行一次dfs explore -> for loop through board in main method
    • dfs的每一层代表: board上面走的每一步
    • candidates: 这个char上下左右的4个char
    • filter
      • 没有被visited
      • 下一个char存在于trie里面
    • stop
      • 当trieNode是一个词的时候, 把它加入到res中. 注意!!! 这里并不STOP, 应该继续dfs
    • backtracking: remove empty trieNode
  • build trie: 略
    • 这里只需要children, word即可
    • implement add, 不需要find/search/isPrefix

SpaceComplexity => O(L * N + R*C)

  • Trie: O(L * N) all the char counts in the words
  • visited hashSet: O(R*C)

TimeComplexity: L: average word length / N: words.length

  • build trie: O(L * N)
  • dfs => O(R*C*4L + L*N)
    • for loop in main method: O(R*C) -> loop through each cell in the board
    • each dfs: O(4^L) -> need to explore 4 directions for an average of L times
      • 另外一种是O(4 * 3L-1) => 因为只有第一个cell需要explore 4个方向, 之后都只要explore3个方向, exclude来时的方向
    • worst case: 当board里面全是a且dictionary 里面有一个词是”aaaaa”的话dfs就是worst case
public List<String> findWords(char[][] board, String[] words) {
    Trie trie = new Trie(words);
    List<String> res = new ArrayList<>();
    int m = board.length, n = board[0].length;
    for(int i = 0; i < m; i ++) {
        for(int j = 0; j < n; j ++) {
            if (trie.getRoot().children.containsKey(board[i][j])) {
                helper(i, j, new HashSet<Integer>(), board, res, trie.getRoot());
            }
        }
    }
    return res;
}
private int[][] dirs = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private void helper(int x, int y, Set<Integer> path, char[][] board, List<String> res, TrieNode parent) {
    char c = board[x][y];
    TrieNode node = parent.children.get(c);
    if (node.word.length() > 0) {
        res.add(node.word);
        // So that it will not find same word again
        node.word = "";
    }
    int curIndex = x * board[0].length + y;
    path.add(curIndex);
    for(int[] dir : dirs) {
        int i = x + dir[0];
        int j = y + dir[1];
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || path.contains(i * board[0].length + j) || !node.children.containsKey(board[i][j])) continue;
        helper(i, j, path, board, res, node);
    }
    path.remove(curIndex);
    // trim trie
    if(node.children.size() == 0) {
        parent.children.remove(c);
    }
}

Leave a comment