【图论】Leetcode 208. 实现 Trie (前缀树)【中等】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【图论】Leetcode 208. 实现 Trie (前缀树)【中等】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

实现 Trie (前缀树)

Trie（发音类似 “try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True

解题思路

使用Trie树来实现前缀树。
1、Trie树是一个多叉树，每个节点有26个子节点，表示26个小写字母。
2、每个节点除了指向子节点的指针外，还需要一个标志位，表示当前节点是否是一个单词的结束。
3、插入字符串时，从根节点开始遍历，依次将字符串的每个字符插入对应的子节点中，如果到达字符串末尾，将标志位设置为true。
4、搜索字符串时，从根节点开始遍历，依次查找对应的子节点，如果遇到空节点或者到达字符串末尾但标志位为false，则返回false，否则返回true。
5、搜索前缀时，与搜索字符串类似，不同之处在于即使到达字符串末尾，只要存在子节点，即返回true。
就是 Trie 类有一个 TrieNode 内部类，用于表示 Trie 的节点。
TrieNode 类包含了一个包含26个链接的数组，代表了从当前节点出发的所有可能的字符路径，进行嵌套链接节点（类似于链表，只不过里面是节点集合）。

Java实现

class TrieNode {
    private TrieNode[] links;
    private final int R = 26;
    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[R];
    }

    /**
     * 这个代码段是在 Trie 数据结构中用来判断是否存在以字符 ch 为结尾的节点的链接。
     * Trie 是一种树形数据结构，用于高效地存储和检索字符串集合中的键。
     *
     * 在 Trie 中，每个节点表示一个字符，从根节点到某个节点的路径上所经过的字符连接起来，
     * 就是该节点所代表的字符串。因此，对于每个节点，我们需要存储一个数组 links，
     * 数组的长度通常是字符集的大小（比如小写字母表为 26），
     * 数组的每个元素表示当前节点连接到的下一个节点。
     *
     * 因此，代码段 links[ch - 'a'] != null 的含义是判断在当前节点的 links
     * 数组中是否存在以字符 ch 为结尾的链接。如果 links[ch - 'a'] 不为 null，
     * 则表示存在以字符 ch 结尾的链接，否则表示不存在。
     * @param ch
     * @return
     */
    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }

    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (node.containsKey(currentChar)) {
                node = node.get(currentChar);
            } else {
                return null;
            }
        }
        return node;
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
    public static void main(String[] args) {
        Trie trie = new Trie();

        // Test insert
        trie.insert("apple");
        trie.insert("banana");
        trie.insert("orange");

        // Test search
        System.out.println(trie.search("apple"));   // Output: true
        System.out.println(trie.search("orange"));  // Output: true
        System.out.println(trie.search("banana"));  // Output: true
        System.out.println(trie.search("grape"));   // Output: false

        // Test startsWith
        System.out.println(trie.startsWith("app"));  // Output: true
        System.out.println(trie.startsWith("ban"));  // Output: true
        System.out.println(trie.startsWith("ora"));  // Output: true
        System.out.println(trie.startsWith("gr"));   // Output: false
    }
}