前缀树(字典树/Trie) -----Java实现

╰半橙微兮° 2024-03-25 20:32 107阅读 0赞

**目录**

一.前缀树

1.什么是前缀树

2.前缀树的举例

二.前缀树的实现

1.前缀树的数据结构

1.插入字符串

2.查找字符串

3.查找前缀

三.词典中最长的单词

1.题目描述

2.问题分析

3.代码实现

--------------------

## 一.前缀树 ##

### 1.什么是前缀树 ###

字典树（Trie树）是一种**树形数据结构**，常用于**字符串的存储和查找**。字典树的核心思想是**利用字符串之间的公共前缀来节省存储空间和提高查询效率**。它是一棵**多叉树**，每个**节点**代表一个**字符串的前缀**，从**根节点到叶子节点的路径组成一个字符串**。

字典树的**根节点不包含字符**，每个**子节点代表一个字符**，从根节点到任意一个节点所经过的路径上的字符连接起来即为该节点所代表的字符串。每个节点可以存储一个或多个字符串，通常使用一个**标志来标记一个节点代表的字符串是否存在**。当需要在一组字符串中查找某个字符串时，可以利用字典树来实现高效的查找操作。

### **2.前缀树的举例** ###

例如对字符串数组\{"goog","google","bai","baidu","a"\}建立前缀树,此时我们可以很清晰的看到前缀树的一些特征:

*  根结点不保存字符
 *  前缀树是一颗多叉树
 *  前缀树的每个节点保存一个字符
 *  具有相同前缀的字符串保存在同一条路径上
 *  字符串的尾处相应的在前缀树上也有结束的标志

![435cb15b7e4a4612a00b535b998d7689.png][]

## 二.前缀树的实现 ##

力扣上的208题就是实现前缀树:[力扣][Link 1]

### 1.前缀树的数据结构 ###

在写代码的时候,我偏向于用**哈希表来存储结点的信息**,有的也可以用**数组来存储结点的信息**,本质上都是一样的

public class Trie {
        Map<Character, Trie> next;
        boolean isEnd;
    
        public Trie() {
            this.next = new HashMap<>();
            this.isEnd = false;
        }
    
    
        public void insert(String word) {
    
        }
    
        public boolean search(String word) {
            return false;
    
        }
    
        public boolean startsWith(String prefix) {
            return false;
    
        }
    }

### 1.插入字符串 ###

public void insert(String word) {
            Trie trie = this;//获得根结点
            for (char c : word.toCharArray()) {
                if (trie.next.get(c) == null) {//当前结点不存在
                    trie.next.put(c, new Trie());//创建当前结点
                }
                trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
            }
            trie.isEnd = true;
    
        }

### 2.查找字符串 ###

public boolean search(String word) {
            Trie trie = this;//获得根结点
            for (char c : word.toCharArray()) {
                if (trie.next.get(c) == null) {//当前结点不存在
                    return false;
                }
                trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
            }
            return trie.isEnd;
    
        }

### 3.查找前缀 ###

public boolean startsWith(String prefix) {
            Trie trie = this;//获得根结点
            for (char c : prefix.toCharArray()) {
                if (trie.next.get(c) == null) {//当前结点不存在
                    return false;
                }
                trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
            }
            return true;
    
        }

接下来是力扣上关于前缀树的一些题目

## 三.词典中最长的单词 ##

### 1.题目描述 ###

> 给出一个字符串数组 `words` 组成的一本英语词典。返回 `words` 中最长的一个单词，该单词是由 `words` 词典中其他单词逐步添加一个字母组成。
> 
> 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

力扣:[力扣][Link 2]

### 2.问题分析 ###

这是一道典型的前缀树的问题,但是这一题有一些特殊的要求,返回的答案是:

**1.最长的单词 2.这个单词由其他单词逐步构成 3.长度相同返回字典序小的**

因此我们需要对前缀树的相关代码进行修改,把字符串一一插入的代码还是不改变的,主要修改的是查找的代码,应该在 trie.next.get(c) == null在增加一个判断为false的条件,就是每一个结点都应该有一个标志true,表示每个节点都存在一个单词,最终一步步构成最长的单词(叶子结点的单词)

### 3.代码实现 ###

class Solution {
        public String longestWord(String[] words) {
            Trie trie = new Trie();
            for (String word : words) {
                trie.insert(word);
            }
            String longest = "";
            for (String word : words) {
                if (trie.search(word)) {
                    if (word.length() > longest.length() || ((word.length() == longest.length()) && (word.compareTo(longest) < 0))) {
                        longest = word;
                    }
    
                }
            }
            return longest;
        }
    }
    class Trie {
        Map<Character, Trie> next;
        boolean isEnd;
    
        public Trie() {
            this.next = new HashMap<>();
            this.isEnd = false;
        }
    
    
        public void insert(String word) {
            Trie trie = this;//获得根结点
            for (char c : word.toCharArray()) {
                if (trie.next.get(c) == null) {//当前结点不存在
                    trie.next.put(c, new Trie());//创建当前结点
                }
                trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
            }
            trie.isEnd = true;
    
        }
    
        public boolean search(String word) {
            Trie trie = this;//获得根结点
            for (char c : word.toCharArray()) {
                if (trie.next.get(c) == null || !trie.next.get(c).isEnd) {//当前结点不存在
                    return false;
                }
                trie = trie.next.get(c);//得到字符c的结点,继续向下遍历
            }
            return trie.isEnd;
    
        }
    
    }

[435cb15b7e4a4612a00b535b998d7689.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/34263a0dcfa445bc9df65ab9067b9e8a.png
[Link 1]: https://leetcode.cn/problems/implement-trie-prefix-tree/
[Link 2]: https://leetcode.cn/problems/longest-word-in-dictionary/description/