小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。
今天小史去了一家在线英语培训公司面试了。
简单的自我介绍后，面试官给了小史一个问题。
【五分钟学算法面试现场】
题目：我有500w个单词，你帮忙设计一个数据结构来进行存储，存好之后，我有两个需求。
1、来了一个新的单词，需要判断是否在这500w个单词中
2、来了一个单词前缀，给出500w个单词中有多少个单词是该前缀
小史这次没有不假思索就给出回答，他学会了深沉。
小史回忆起吕老师之前教他的bitmap算法。
小史心想：bitmap可以判断一个数是否在40亿个int32数中，其核心是每一个数映射成一个位，同时申请的bit位数覆盖了整个int32的值域。
小史在纸上算了半天，终于开口了。
小史：好的，我用bitmap来做第一问。我把每一个字符串映射成一个位。比如，a是第1位，b是第2位，z是第26位，aa是第27位，ab是第28位，以此类推。英文一共26个字母，我算了一下，6个字符长度的单词总共有26的6次方个，需要占26的6次方个位，大概300M。
小史：建立数据结构的时候，排序需要花掉nlg(n)，排序时字符串比较花掉m，时间一共mnlg(n)。查找的话用二分，就是mlg(n)了。空间是mn。
一分钟过去了。
【请教大神】
回到学校，小史把面试情况和吕老师说了一下。
吕老师：你想想，a到z这26个字母中，可能只有a和i两个是单词，其他都不是，所以你的bitmap大量空间都被浪费了。这种情况你搞个hashset没准还更省一点。
【树形结构解难题】
小史：哦，这确实是节省了空间，如果要找单词interest，那么就找根节点了，如果是找单词interesting，那么就从根节点往下走，再把沿路的字母们都拼起来就行了。
（注：这里说的in不是单词，指的是in不是500w单词中的单词）
吕老师还没说完，小史就打断了他。
找单词interest：
找前缀为inter的所有单词：
遍历以前缀节点为根结点的一棵树，就能统计出前缀为inter的所有单词有多少个。
【字典树】
小史：节点中增加一个变量用于计数，在添加节点的时候，就把相应的计数+1
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
DictionaryTree.java
import java.util.HashMap;
import java.util.Map;
/**
* @author xiaoshi on 2018/10/5.
*/
public class DictionaryTree {
// 字典树的节点
private class Node {
// 是否是单词
private boolean isWord;
// 单词计数
private int count;
// 字串
private String str;
// 子节点
private Map<String, Node> childs;
// 父节点
private Node parent;
public Node() {
childs = new HashMap<String, Node>();
}
public Node(boolean isWord, int count, String str) {
this();
this.isWord = isWord;
this.count = count;
this.str = str;
}
public void addChild(String key, Node node) {
childs.put(key, node);
node.parent = this;
}
public void removeChild(String key) {
childs.remove(key);
}
public String toString() {
return "str : " + str + ", isWord : " + isWord + ", count : " + count;
}
}
// 字典树根节点
private Node root;
DictionaryTree() {
// 初始化root
root = new Node();
}
// 添加字串
private void addStr(String word, Node node) {
// 计数
node.count++;
String str = node.str;
if(null != str) {
// 寻找公共前缀
String commonPrefix = "";
for(int i=0; i<word.length(); i++) {
if(str.length() > i && word.charAt(i) == str.charAt(i)) {
commonPrefix += word.charAt(i);
} else {
break;
}
}
// 找到公共前缀
if(commonPrefix.length() > 0) {
if (commonPrefix.length() == str.length() && commonPrefix.length() == word.length()) {
// 与之前的词重复
} else if(commonPrefix.length() == str.length() && commonPrefix.length() < word.length()) {
// 剩余的串
String wordLeft = word.substring(commonPrefix.length());
// 剩余的串去子节点中继续找
searchChild(wordLeft, node);
} else if(commonPrefix.length() < str.length()) {
// 节点裂变
Node splitNode = new Node(true, node.count, commonPrefix);
// 处理裂变节点的父关系
splitNode.parent = node.parent;
splitNode.parent.addChild(commonPrefix, splitNode);
node.parent.removeChild(node.str);
node.count--;
// 节点裂变后的剩余字串
String strLeft = str.substring(commonPrefix.length());
node.str = strLeft;
splitNode.addChild(strLeft, node);
// 单词裂变后的剩余字串
if(commonPrefix.length() < word.length()) {
splitNode.isWord = false;
String wordLeft = word.substring(commonPrefix.length());
Node leftNode = new Node(true, 1, wordLeft);
splitNode.addChild(wordLeft, leftNode);
}
}
} else {
// 没有共同前缀，直接添加节点
Node newNode = new Node(true, 1, word);
node.addChild(word, newNode);
}
} else {
// 根结点
if(node.childs.size() > 0) {
searchChild(word, node);
} else {
Node newNode = new Node(true, 1, word);
node.addChild(word, newNode);
}
}
}
// 在子节点中添加字串
public void searchChild(String wordLeft, Node node) {
boolean isFind = false;
if(node.childs.size() > 0) {
// 遍历孩子
for(String childKey : node.childs.keySet()) {
Node childNode = node.childs.get(childKey);
// 首字母相同，则在该子节点继续添加字串
if(wordLeft.charAt(0) == childNode.str.charAt(0)) {
isFind = true;
addStr(wordLeft, childNode);
break;
}
}
}
// 没有首字母相同的孩子，则将其变为子节点
if(!isFind) {
Node newNode = new Node(true, 1, wordLeft);
node.addChild(wordLeft, newNode);
}
}
// 添加单词
public void add(String word) {
addStr(word, root);
}
// 在节点中查找字串
private boolean findStr(String word, Node node) {
boolean isMatch = true;
String wordLeft = word;
String str = node.str;
if(null != str) {
// 字串与单词不匹配
if(word.indexOf(str) != 0) {
isMatch = false;
} else {
// 匹配，则计算剩余单词
wordLeft = word.substring(str.length());
}
}
// 如果匹配
if(isMatch) {
// 如果还有剩余单词长度
if(wordLeft.length() > 0) {
// 遍历孩子继续找
for(String key : node.childs.keySet()) {
Node childNode = node.childs.get(key);
boolean isChildFind = findStr(wordLeft, childNode);
if(isChildFind) {
return true;
}
}
return false;
} else {
// 没有剩余单词长度，说明已经匹配完毕，直接返回节点是否为单词
return node.isWord;
}
}
return false;
}
// 查找单词
public boolean find(String word) {
return findStr(word, root);
}
// 统计子节点字串单词数
private int countChildStr(String prefix, Node node) {
// 遍历孩子
for(String key : node.childs.keySet()) {
Node childNode = node.childs.get(key);
// 匹配子节点
int childCount = countStr(prefix, childNode);
if(childCount != 0) {
return childCount;
}
}
return 0;
}
// 统计字串单词数
private int countStr(String prefix, Node node) {
String str = node.str;
// 非根结点
if(null != str) {
// 前缀与字串不匹配
if(prefix.indexOf(str) != 0 && str.indexOf(prefix) != 0) {
return 0;
// 前缀匹配字串，且前缀较短
} else if(str.indexOf(prefix) == 0) {
// 找到目标节点，返回单词数
return node.count;
// 前缀匹配字串，且字串较短
} else if(prefix.indexOf(str) == 0) {
// 剩余字串继续匹配子节点
String prefixLeft = prefix.substring(str.length());
if(prefixLeft.length() > 0) {
return countChildStr(prefixLeft, node);
}
}
} else {
// 根结点，直接找其子孙
return countChildStr(prefix, node);
}
return 0;
}
// 统计前缀单词数
public int count(String prefix) {
// 处理特殊情况
if(null == prefix || prefix.trim().isEmpty()) {
return root.count;
}
// 从根结点往下匹配
return countStr(prefix, root);
}
// 打印节点
private void printNode(Node node, int layer) {
// 层级递进
for(int i=0; i<layer; i++) {
System.out.print("t");
}
// 打印
System.out.println(node);
// 递归打印子节点
for (String str : node.childs.keySet()) {
Node child = node.childs.get(str);
printNode(child, layer + 1);
}
}
// 打印字典树
public void print() {
printNode(root, 0);
}
}
(友情提示：可左右滑动)
Main.java
/**
* @author xiaoshi on 2018/10/5.
*/
public class Main {
public static void main(String[] args) {
DictionaryTree dt = new DictionaryTree();
dt.add("interest");
dt.add("interesting");
dt.add("interested");
dt.add("inside");
dt.add("insert");
dt.add("apple");
dt.add("inter");
dt.add("interesting");
dt.print();
boolean isFind = dt.find("inside");
System.out.println("find inside : " + isFind);
int count = dt.count("inter");
System.out.println("count prefix inter : " + count);
}
}
(友情提示：可左右滑动)
运行结果
str : null, isWord : false, count : 8
str : apple, isWord : true, count : 1
str : in, isWord : false, count : 7
str : ter, isWord : true, count : 5
str : est, isWord : true, count : 4
str : ing, isWord : true, count : 2
str : ed, isWord : true, count : 1
str : s, isWord : false, count : 2
str : ert, isWord : true, count : 1
str : ide, isWord : true, count : 1
find inside : true
count prefix inter : 5
(友情提示：可左右滑动)
【字典树的应用】
小史：我想想啊，大量字符串的统计和查找应该就可以用字典树吧？字符串前缀的匹配也可以用，像咱们搜索常见的autoComplete控件是不是就可以用？
五分钟学算法面试现场是互联网侦察推出的一个新的板块，旨在回放真实的面试过程，并对面试题进行全面解析，提供多种思路，比较优劣，希望对大家的面试有所帮助。
往期回顾
【五分钟学算法面试现场】如何判断一个数是否在40亿个整数中？
原文始发于微信公众号（互联网侦察）：【五分钟学算法面试现场】如何在500w个单词中统计特定前缀的单词有多少个？
