[数据结构与算法]高级数据结构之前缀树

3、前缀树

模板

import java.util.LinkedList;
import java.util.List;

/**
 * @author Lucas
 * @create 2022-04-03 18:11
 */
public class TrieMap<V> {
    // ASCII 码个数
    private static final int R = 256;
    // 当前存在 Map 中的键值对个数
    private static int size = 0;
    // Trie 树的根节点
    private TrieNode<V> root = null;

    private static class TrieNode<V> {
        V val = null;
        TrieNode<V>[] children = new TrieNode[R];
    }

    /***** 增/改 *****/

    // 在 map 中添加或修改键值对
    public TrieNode<V> put(String key, V val) {
        if (!containsKey(key)) {
            // 新增键值对
            size++;
        }
        // 需要一个额外的辅助函数，并接收其返回值
        root = put(root, key, val, 0);
        return root;
    }

    // 定义：向以 node 为根的 Trie 树中插入 key[i..]，返回插入完成后的根节点
    private TrieNode<V> put(TrieNode<V> node, String key, V val, int i) {
        // 如果树枝不存在，新建
        if (node == null) {
            node = new TrieNode<>();
        }
        if (i == key.length()) {
            // key 的路径已插入完成，将值 val 存入节点
            node.val = val;
            return node;
        }
        char c = key.charAt(i);
        // 递归插入子节点，并接收返回值
        node.children[c] = put(node.children[c], key, val, i + 1);
        return node;
    }

    /***** 删 *****/

    // 在 Map 中删除 key
    public TrieNode<V> remove(String key) {
        if (!containsKey(key)) {
            return null;
        }
        // 递归修改数据结构要接收函数的返回值
        root = remove(root, key, 0);
        return root;
    }

    // 定义：在以 node 为根的 Trie 树中删除 key[i..]，返回删除后的根节点
    private TrieNode<V> remove(TrieNode<V> node, String key, int i) {
        if (node == null) {
            return null;
        }
        if (i == key.length()) {
            // 找到了 key 对应的 TrieNode，删除 val
            node.val = null;
            return null;
        }
        char c = key.charAt(i);
        // 递归去子树进行删除
        node.children[c] = remove(node.children[c], key, i + 1);
        // 后序位置，递归路径上的节点可能需要被清理
        if (node.val != null) {
            // 如果该 TireNode 存储着 val，不需要被清理
            return node;
        }
        // 检查该 TrieNode 是否还有后缀
        for (char d = 0; d < R; d++) {
            if (node.children[d] != null) {
                // 只要存在一个子节点（后缀树枝），就不需要被清理
                return node;
            }
        }
        // 既没有存储 val，也没有后缀树枝，则该节点需要被清理
        return null;
    }

    // 从节点 node 开始搜索 key，如果存在返回对应节点，否则返回 null
    private TrieNode<V> getNode(TrieNode node, String key) {
        TrieNode p = node;
        // 从节点 node 开始搜索 key
        for (int i = 0; i < key.length(); i++) {
            if (p == null) {
                // 无法向下搜索
                return null;
            }
            // 向下搜索
            char c = key.charAt(i);
            p = p.children[c];
        }
        return p;
    }

    /***** 查 *****/

    // 搜索 key 对应的值，不存在则返回 null
    public V get(String key) {
        // 从 root 开始搜索 key
        TrieNode<V> x = getNode(root, key);
        if (x != null && x.val != null) {
            // x 为空或 x 的 val 字段为空都说明 key 没有对应的值
            return x.val;
        }
        return null;
    }

    // 判断 key 是否存在在 Map 中
    public boolean containsKey(String key) {
        return get(key) != null;
    }

    // 判断是和否存在前缀为 prefix 的键
    public boolean containsPrefix(String prefix) {
        // 只要能找到一个节点，就是存在前缀
        return getNode(root, prefix) != null;
    }

    // 在所有键中寻找 query 的最短前缀
    public String shortestPrefix(String query) {
        TrieNode<V> p = this.root;
        // 从节点 node 开始搜索 key
        for (int i = 0; i < query.length(); i++) {
            if (p == null) {
                // 无法向下搜索
                return null;
            }
            if (p.val != null) {
                // 找到一个键是 query 的前缀
                return query.substring(0, i);
            }
            // 向下搜索
            char c = query.charAt(i);
            p = p.children[c];
        }
        if (p != null && p.val != null) {
            // 如果 query 本身就是一个键
            return query;
        }
        return null;
    }

    // 在所有键中寻找 query 的最长前缀
    public String longestPrefix(String query) {
        TrieNode<V> p = this.root;
        // 记录前缀的最大长度
        int max_len = 0;
        // 从节点 node 开始搜索 key
        for (int i = 0; i < query.length(); i++) {
            if (p == null) {
                // 无法向下搜索
                break;
            }
            if (p.val != null) {
                // 找到一个键是 query 的前缀，更新前缀的最大长度
                max_len = i;
            }
            // 向下搜索
            char c = query.charAt(i);
            p = p.children[c];
        }
        if (p != null && p.val != null) {
            // 如果 query 本身就是一个键
            return query;
        }
        return query.substring(0, max_len);
    }

    // 搜索前缀为 prefix 的所有键
    public List<String> keysWithPrefixOf(String prefix) {
        List<String> res = new LinkedList<>();
        // 找到匹配 prefix 在 Trie 树中的那个节点
        TrieNode<V> x = getNode(root, prefix);
        // DFS 遍历以 x 为根的这棵 Trie 树
        traverse(x, new StringBuffer(prefix), res);
        return res;
    }

    // 遍历以 node 节点为根的 Trie 树，找到所有键
    private void traverse(TrieNode<V> node, StringBuffer path, List<String> res) {
        if (node == null) {
            // 到达 Trie 树底部叶子结点
            return;
        }
        if (node.val != null) {
            // 找到一个 key，添加到结果列表中
            res.add(path.toString());
        }
        // 回溯算法遍历框架
        for (char c = 0; c < R; c++) {
            // 做选择
            path.append(c);
            traverse(node.children[c], path, res);
            // 撤销选择
            path.deleteCharAt(path.length() - 1);
        }
    }

    // 通配符 . 匹配任意字符
    public List<String> keysWithPattern(String pattern) {
        List<String> res = new LinkedList<>();
        traverse(root, new StringBuffer(), res, pattern, 0);
        return res;
    }

    // 遍历函数，尝试在「以 node 为根的 Trie 树中」匹配 pattern[i..]
    private void traverse(TrieNode<V> node, StringBuffer path, List<String> res, String pattern, int i) {
        if (node == null) {
            // 树枝不存在，即匹配失败
            return;
        }
        if (i == pattern.length()) {
            // pattern 匹配完成
            if (node.val != null) {
                // 如果这个节点存储着 val，则找到一个匹配的键
                res.add(path.toString());
            }
            return;
        }
        char c = pattern.charAt(i);
        if (c == '.') {
            // pattern[i] 是通配符，可以变化成任意字符
            // 多叉树（回溯算法）遍历框架
            for (char d = 0; d < R; d++) {
                path.append(d);
                traverse(node.children[d], path, res, pattern, i + 1);
                path.deleteCharAt(path.length() - 1);
            }
        } else {
            // pattern[i] 是普通字符 c
            path.append(c);
            traverse(node.children[c], path, res, pattern, i + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }

    public boolean hasKeyWithPattern(String pattern) {
        return traverse(root, pattern, 0);
    }

    private boolean traverse(TrieNode<V> node, String pattern, int i) {
        if (node == null) {
            return false;
        }
        if (i == pattern.length()) {
            if (node.val != null) {
                return true;
            }
            return false;
        }
        char c = pattern.charAt(i);
        if (c == '.') {
            for (char d = 97; d < 97 + 26; d++) {
                if (node.children[d] != null) {
                    if (traverse(node.children[d], pattern, i + 1)) return true;
                }
            }
        } else {
            if (traverse(node.children[c], pattern, i + 1)) return true;
        }
        return false;
    }
}

208. 实现 Trie (前缀树)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Jo6nwjY2-1648990807585)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/13ecf4ef-9d7e-49a7-b671-71b09b28adeb/Untitled.png)]

### 解题思路
此处撰写解题思路

### 代码

```java
class Trie {
    private final TrieMap<Object> map = new TrieMap<>();

    public Trie() {

    }

    public void insert(String word) {
        map.put(word, new Object());
    }

    public boolean search(String word) {
        return map.containsKey(word);
    }

    public boolean startsWith(String prefix) {
        return map.containsPrefix(prefix);
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

648. 单词替换

class Solution {
    private TrieMap<Object> map = new TrieMap<Object>();

    public String replaceWords(List<String> dictionary, String sentence) {
        for (int i = 0; i < dictionary.size(); i++) {
            map.put(dictionary.get(i), new Object());
        }
        String[] split = sentence.split("\\s+");
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < split.length; i++) {
            String str = map.shortestPrefix(split[i]);
            if (str == null) {
                sb.append(split[i]);
            } else {
                sb.append(str);
            }
            if (i != split.length - 1) {
                sb.append(' ');
            }
        }
        return sb.toString();
    }
}

211. 添加与搜索单词 - 数据结构设计

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q3xxG673-1648990807586)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d81bee25-ab40-410d-b47f-064e9305fe39/Untitled.png)]

class WordDictionary {
    TrieMap<Object> map = new TrieMap<>();

    public WordDictionary() {

    }

    public void addWord(String word) {
        map.put(word, new Object());
    }

    public boolean search(String word) {
        return map.hasKeyWithPattern(word);
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

677. 键值映射

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OZPeg37C-1648990807587)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/47375219-2b43-47a7-9f4e-b4ba187105c2/Untitled.png)]

class MapSum {
    TrieMap<Integer> map;

    public MapSum() {
        map = new TrieMap<>();
    }

    public void insert(String key, int val) {
        map.put(key, val);
    }

    public int sum(String prefix) {
        List<String> list = map.keysWithPrefixOf(prefix);
        int sum = 0;
        for (String s : list) {
            Integer x = map.get(s);
            sum += x;
        }
        return sum;
    }
}
/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */