leetcode面试准备:Implement Trie (Prefix Tree)

时间:2023-03-08 22:25:57

leetcode面试准备:Implement Trie (Prefix Tree)

1 题目

Implement a trie with insert, search, and startsWith methods.

Note:

You may assume that all inputs are consist of lowercase letters a-z.

2 思路

该题是实现trie树。

Trie,又称单词查找树或键树,是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

它有3个基本性质:

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

此外,每个节点存在一个判断其是否是一个单词结尾的标记,用来表明该trie树中包含该单词。因此我们首先需要定义节点的数据结构。

节点的属性主要包含以下几点:

  • char content:节点字符内容
  • boolean isEnd:节点是否为一个单词结束的标记
  • LinkedList<TrieNode> childNode: 该节点的所有的孩子节点

leetcode面试准备:Implement Trie (Prefix Tree)

3 代码

TrieNode

import java.util.LinkedList;

public class TrieNode {
// Initialize your data structure here.
char content; // 节点内容
boolean isEnd;// 是否为一个单词的结尾
LinkedList<TrieNode> childNode;// 该节点所有的孩子节点 // Initialize your data structure here.
public TrieNode() {
this.content = 0;
this.isEnd = false;
this.childNode = new LinkedList<TrieNode>();
} public TrieNode(char content) {
this.content = content;
this.isEnd = false;
this.childNode = new LinkedList<TrieNode>();
} public TrieNode subNode(char c) {
for (TrieNode tn : childNode) {
if (tn.content == c) {
return tn;
}
}
return null;
} @Override
public String toString() {
return ("content:" + content + "\n child:" + childNode.toString());
}
}

Trie

public class Trie {
// 字典树的实现,效率高于HashMap
private TrieNode root; public Trie() {
root = new TrieNode();
} // Inserts a word into the trie.
public void insert(String word) {
if (search(word)) {
return;
}
int len = word.length();
TrieNode cur = root;
for (int i = 0; i < len; i++) {
char c = word.charAt(i);
TrieNode tmp = cur.subNode(c);
if (tmp == null) {
tmp = new TrieNode(c);
cur.childNode.add(tmp);
cur = tmp;
} else {
cur = tmp;
}
}
cur.isEnd = true;
} // Returns if the word is in the trie.
public boolean search(String word) {
int len = word.length();
TrieNode cur = root;
for (int i = 0; i < len; i++) {
char c = word.charAt(i);
TrieNode tmp = cur.subNode(c);
if (tmp == null) {
return false;
} else {
cur = tmp;
}
}
return cur.isEnd;
} // Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
int len = prefix.length();
TrieNode cur = root;
for (int i = 0; i < len; i++) {
char c = prefix.charAt(i);
TrieNode tmp = cur.subNode(c);
if (tmp == null) {
return false;
} else {
cur = tmp;
}
}
return true;
} public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("somestring");
trie.insert("key");
boolean res = trie.startsWith("ke");
System.out.println(res);
}
} // Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

4 总结

很不错的问题,估计面试网易有道,360,百度这样的企业会考到。