The dictionary tree is similar to a binary tree, and its internal structure is not complex. In terms of prefix, try bailing, but there are not as many changes as red black tree and AVL. Code it quickly

1, Introduction to dictionary tree

The dictionary tree is not dead. In fact, it is changeable. In the introduction, we will explain the possible variants

1. Define node
Like a binary tree, a node needs to store its data and the of the next node. If the node contains only letters, we have two ways to connect to the next node

HashMap type: HashMap is used in Node to connect to the next Node, which is applicable to the case of few letter types
Array type: the Node uses an array to connect to the next Node, which is applicable to the case of many letter types

private class Node {
	String word;
	HashMap<Character, Node> child; // hashmap type
}

Explain the function of word: some nodes may only exist as paths (white nodes in the figure above), while others need to store information (red nodes in the figure above), and the storage method can be modified as needed

boolean: can be used to determine whether a word exists
String: you can directly return the found word
int: it can be used to record the number of times the node is accessed, or if there are duplicate words in the dictionary, it can be used to record the number

You can modify the node as needed, and you can also try to compress the path

2. Create root node
The root node is the starting point of the dictionary tree and does not store information

Node root = new Node();

3. Insert method ()
Give a String and insert it into the dictionary tree.
Separate the char s of String one by one, insert them with hashmap, and store the information at the end

public void insert(String word) {
	Node cur = root;
	for (char c : word.toCharArray()) {
		if (!cur.child.containsKey(c))
			cur.child.put(c, new Node);
		cur = cur.child.get(c);
	}
	// At this time, cur is located at the node where the last char of word is located
	cur.word = word;
}

4. Search method ()
Give a String to judge whether it is in the dictionary tree
The method is the same as insert, separating the char of String one by one. If it is not found in hashmap or the last node does not store information, it returns false

public boolean search(String word) {
	Node cur = root;
	for (char c : word.toCharArray()) {
		if (!cur.child.containsKey(c))
			return false;
		cur = cur.child.get(c);
	}
	return cur.word.equals(word);
}

Of course, the insert() and search() methods are very similar. You can try to merge them with formal parameters

2, Dictionary tree practice

1. Topic 1: LeetCode 211 adding and searching words
There is only one change in this question. It can replace words when searching, so the search() method needs special treatment
When. Is encountered, you need to traverse all nodes in hashmap, so search() uses recursion
In addition, since there is no need to return String, the Node can store boolean

private boolean search(Node cur, String word, int i) {
   	if (i == word.length())
        return cur.exist;
    char c = word.charAt(i);
    if (cur.children.containsKey(c)) {
        return search(cur.children.get(c), word, i + 1);
    } else if (c == '.') {
        for (Node child : cur.children.values())
            if (search(child, word, i + 1))
                return true;
    }
    return false;
}

2. Topic 2: LeetCode 212 word search II
Because we want to return all the words we found, the Node needs to be recorded as a String

private class Node {
    String word;
    HashMap<Character, Node> map;
    Node() {
        this.word = null;
        map = new HashMap<>();
    }
}

During initialization, all words are added to the dictionary tree, and insert() does not provide code

final int[] dx = new int[]{0, 1, 0, -1};
final int[] dy = new int[]{1, 0, -1, 0}; // Lower right upper left
boolean[][] visited;
char[][] board;
List<String> ans;
int rows, cols;
Node root;
public List<String> findWords(char[][] board, String[] words) {
    ans = new ArrayList<>();
    root = new Node();
    this.board = board;
    rows = board.length;
    cols = board[0].length;
    for (String s : words)
        insert(s);
}

We use dfs to expand the search, so that the dictionary tree and chessboard search synchronously

private void dfs(Node cur, int x, int y) {  
    if (cur.word != null) {
        ans.add(cur.word);
        cur.word = null; // Prevent repeated addition of the same word
    }
    if (cur.map.isEmpty()) // Judge in advance, prune
        return;
    visited[x][y] = true; 
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || visited[nx][ny] || !cur.map.containsKey(board[nx][ny]))
            continue;
        dfs(cur.map.get(board[nx][ny]), nx, ny);
    }
    visited[x][y] = false; // reduction
}

The above is the basic bfs + backtracking, only with more dictionary trees and one more step of judgment
However, we find that the dictionary tree is redundant. Consider the following situation

When we find aaa, we have obtained the final node data, but we find that the structure of the dictionary tree still exists. We have to go to the bottom node every time. When we find that there is no data, we return step by step, resulting in a lot of redundancy
So we try to delete part of the dictionary tree structure while dfs
When a node's map is empty and there is no data, we delete it from its parent node to eliminate redundancy

private void dfs(Node cur, int x, int y) {
	// cur here is the parent node and child is the child node (that is, the current node)
    Node child = cur.map.get(board[x][y]); 
    if (child.word != null) {
        ans.add(child.word);
        child.word = null;
    }
    if (child.map.isEmpty()) { // Delete part of dictionary tree structure
        cur.map.remove(board[x][y]);
        return;
    }
    visited[x][y] = true;
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || visited[nx][ny] || !cur.map.containsKey(board[nx][ny]))
            continue;
        dfs(child, nx, ny);
    }
    visited[x][y] = false; 
}

4. Practical topic:
LeetCode 208 implements Trie (prefix tree)
LeetCode 14 longest public prefix