LeetCode——208. 实现 Trie (前缀树)

清疚 2023-07-03 12:09 6阅读 0赞

# 208. 实现 Trie (前缀树) #

#### 定义 ####

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]  
**例如：**  
**Trie存储的是单词，查询的时间复杂度是O(w),w为所查询单词的长度；如果使用树结构进行存储，查询的时间复杂度为O(logn)；当存储的单词数量逐渐增多的情况下，树结构查询的时间复杂度是逐渐大于Trie的，而Trie的时间复杂度还是O(w),不会因为存储单词的多少而发生变化。**

#### 局限性 ####

class Node{
        
    public boolean isWord;// 是否为单词结尾
    public TreeMap<Character, Node> next;// 存储节点和字母  使用映射连接每个节点
    }

**最大的问题是空间！**原本存储一个单词使用一个节点的空间，现在每个节点只能存储一个字母，相比之前空间占用成倍上升，解决方法详见压缩字典树Compressed Trie。

## 题目 ##

**实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。**

**示例:**

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

**说明:**  
你可以假设所有的输入都是由小写字母 a-z 构成的。  
保证所有输入均为非空字符串。

#### Trie.java(字典树) ####

import java.util.TreeMap;
    
    //字典树Trie
    public class Trie {
        
    
    	private class Node {
        
    		public boolean isWord;// 是否为单词结尾
    		public TreeMap<Character, Node> next;// 存储节点和字母  使用映射连接每个节点
    
    		public Node(boolean isWord) {
        
    			this.isWord = isWord;
    			next = new TreeMap<>();
    		}
    
    		public Node() {
        
    			// TODO Auto-generated constructor stub
    			this(false);
    		}
    	}
    
    	private Node root;// 根结点
    	private int size;// 存储单词个数
    
    	public Trie() {
        
    		// TODO Auto-generated constructor stub
    		root = new Node();
    		size = 0;
    	}
    
    	public int getSize() {
        
    		return size;
    	}
    
    	// 添加一个新的单词
    	public void insert(String word) {
        
    		Node cur = root;
    		for (int i = 0; i < word.length(); i++) {
        // 遍历单词的字符
    			char c = word.charAt(i);
    			if (cur.next.get(c) == null)// 是否已经包含字符c
    				cur.next.put(c, new Node());// 添加
    			cur = cur.next.get(c);// 如果有，cur指向c
    		}
    		if (!cur.isWord) {
        // 如果这个单词之前没有
    			cur.isWord = true;// 单词结束
    			size++;
    		}
    	}
    
    	// 查询Trie中是否有单词word
    	public boolean search(String word) {
        
    		Node cur = root;
    		for (int i = 0; i < word.length(); i++) {
        
    			char c = word.charAt(i);
    			if (cur.next.get(c) == null)
    				return false;
    			cur = cur.next.get(c);
    		}
    		return cur.isWord;// 判断cur.isWord是否为true
    	}
    
    	// 查询Trie中是否存在prefix为前缀的单词
    	public boolean startsWith(String prefix) {
        
    		Node cur = root;
    		for (int i = 0; i < prefix.length(); i++) {
        
    			char c = prefix.charAt(i);
    			if (cur.next.get(c) == null)
    				return false;
    			cur = cur.next.get(c);
    		}
    		return true;
    	}
    }

#### Main.java(测试) ####

public class Main {
        
    	public static void main(String[] args) {
        
    		Trie t = new Trie();
    		Trie trie = new Trie();
    		trie.insert("apple");
    		System.out.println(trie.search("apple"));  // 返回 true
    		System.out.println(trie.search("app"));     // 返回 false
    		System.out.println(trie.startsWith("app")); // 返回 true
    		trie.insert("app");   
    		System.out.println(trie.search("app")  );   // 返回 true
    	}
    }

**测试结果**  
![在这里插入图片描述][20200206142430540.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200206142530497.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70
[20200206142430540.png]: https://img-blog.csdnimg.cn/20200206142430540.png