Trie树

Trie 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」

https://leetcode.cn/problems/implement-trie-prefix-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-we-esm9/

解决的问题：

快速的查找字符串以及存储字符串：

星号代表标记来作为这是一个单词的结尾，说明单词形成了

一般形式：都是小写字母，都是大写字母，都是数字；一般范围都会比较小

步骤：

假设 word

1. 从根结点开始，遍历单词 word，并看当前字母word[i]是否出现过
   1. 没有 -> 创建一个
   2. 有 -> 遍历到点上
2. 在单词结尾打一个标记

208. 实现 Trie (前缀树)

class Trie {
    class Node {
        Node[] charactersArr;
        boolean isCompleteWord;

        Node() {
            charactersArr = new Node[26];
            this.isCompleteWord = isCompleteWord;
        }
    }

    Node root;
    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        Node p = root;
        for (int i = 0; i < word.length(); i++) {
            char curr = word.charAt(i);
            int idx = curr - 'a';
            if (p.charactersArr[idx] == null) p.charactersArr[idx] = new Node();
            p = p.charactersArr[idx];
        }
        p.isCompleteWord = true;
    }
    
    public boolean search(String word) {
        Node p = root;
        for (int i = 0; i < word.length(); i++) {
            char curr = word.charAt(i);
            int idx = curr - 'a';
            if (p.charactersArr[idx] == null) return false;
            p = p.charactersArr[idx];
        }
        return p.isCompleteWord;
    }
    
    public boolean startsWith(String prefix) {
        Node p = root;
        for (int i = 0; i < prefix.length(); i++) {
            char curr = prefix.charAt(i);
            int idx = curr - 'a';
            if (p.charactersArr[idx] == null) return false;
            p = p.charactersArr[idx];
        }
        return true;
    }
}

/**
 * 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);
 */

1268. 搜索推荐系统

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Arrays.sort(products);
        List<List<String>> ans = new ArrayList<>();
        Trie tr = new Trie();
        for (int i = 0; i < products.length; i++) {
            tr.insert(products[i], i);
        }
        for (int i = 0; i < searchWord.length(); i++) {
            List<String> list = new ArrayList<>();
            int[] idxes = tr.search(searchWord.substring(0, i + 1));
            int l = idxes[0], r = idxes[1];
            for (int j = l; j <= Math.min(l + 2, r) && l != -1; j++) list.add(products[j]);
            ans.add(list);
        }
        return ans;
    }
    class Trie {
        class Node {
            Node[] charArr = new Node[26];
            boolean isCompleted = false;
        }

        Node root;
        Map<Node, Integer> char2MinIdx = new HashMap<>();
        Map<Node, Integer> char2MaxIdx = new HashMap<>();
        Trie() {
            root = new Node();
        }

        public void insert(String product, int wordIdx) {
            Node rootP = root;
            for (int i = 0; i < product.length(); i++) {
                int idx = product.charAt(i) - 'a';
                if (rootP.charArr[idx] == null) {
                    rootP.charArr[idx] = new Node();
                    char2MinIdx.put(rootP.charArr[idx], wordIdx);
                }
                char2MaxIdx.put(rootP.charArr[idx], wordIdx);
                rootP = rootP.charArr[idx];
            }
            rootP.isCompleted = true;
        }

        public int[] search(String target) {
            Node rootP = root;
            int l = -1, r = -1;
            for (int i = 0; i < target.length(); i++) {
                int idx = target.charAt(i) - 'a';
                if (rootP.charArr[idx] == null) return new int[]{-1, -1};
                l = char2MinIdx.get(rootP.charArr[idx]);
                r = char2MaxIdx.get(rootP.charArr[idx]);
                rootP = rootP.charArr[idx];
            }
            return new int[] {l, r};
        }
    }
}