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

208. 实现 Trie (前缀树)

定义

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

例如：
Trie存储的是单词，查询的时间复杂度是O(w),w为所查询单词的长度；如果使用树结构进行存储，查询的时间复杂度为O(logn)；当存储的单词数量逐渐增多的情况下，树结构查询的时间复杂度是逐渐大于Trie的，而Trie的时间复杂度还是O(w),不会因为存储单词的多少而发生变化。

题目

实现一个 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
	}
}

测试结果