1
【面试现场】如何在500w个单词中统计特定前缀的单词有多少个？
source link: https://www.cxyxiaowu.com/5856.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【面试现场】如何在500w个单词中统计特定前缀的单词有多少个？
小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进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个单词中统计特定前缀的单词有多少个？
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK