今天小史去了一家在线英语培训公司面试了。

简单的自我介绍后,面试官给了小史一个问题。

题目:我有500w个单词,你帮忙设计一个数据结构来进行存储,存好之后,我有两个需求。

1、来了一个新的单词,需要判断是否在这500w个单词中

2、来了一个单词前缀,给出500w个单词中有多少个单词是该前缀

小史这次没有不假思索就给出回答,他学会了深沉。

小史回忆起吕老师之前教他的bitmap算法。

小史心想:bitmap可以判断一个数是否在40亿个int32数中,其核心是每一个数映射成一个位,同时申请的bit位数覆盖了整个int32的值域。

小史在纸上算了半天,终于开口了。

小史:好的,我用bitmap来做第一问。我把每一个字符串映射成一个位。比如,a是第1位,b是第2位,z是第26位,aa是第27位,ab是第28位,以此类推。英文一共26个字母,我算了一下,6个字符长度的单词总共有266次方个,需要占266次方个位,大概300M

小史:建立数据结构的时候,排序需要花掉nlg(n),排序时字符串比较花掉m,时间一共mnlg(n)。查找的话用二分,就是mlg(n)了。空间是mn

一分钟过去了。

回到学校,小史把面试情况和吕老师说了一下。

吕老师:你想想,az26个字母中,可能只有ai两个是单词,其他都不是,所以你的bitmap大量空间都被浪费了。这种情况你搞个hashset没准还更省一点。

【树形结构解难题】

小史:哦,这确实是节省了空间,如果要找单词interest,那么就找根节点了,如果是找单词interesting,那么就从根节点往下走,再把沿路的字母们都拼起来就行了。

(注:这里说的in不是单词,指的是in不是500w单词中的单词)

吕老师还没说完,小史就打断了他。

找单词interest:

找前缀为inter的所有单词:

遍历以前缀节点为根结点的一棵树,就能统计出前缀为inter的所有单词有多少个。

【字典树】

小史:节点中增加一个变量用于计数,在添加节点的时候,就把相应的计数+1

DictionaryTree.java

importjava.util.HashMap;

importjava.util.Map;

/**

@authorxiaoshi on 2018/10/5.

*/

publicclassDictionaryTree{

// 字典树的节点

privateclassNode{

// 是否是单词

privatebooleanisWord;

// 单词计数

privateintcount;

// 字串

privateString str;

// 子节点

privateMap<String, Node> childs;

// 父节点

privateNode parent;

publicNode(){

childs = newHashMap<String, Node>();

}

publicNode(booleanisWord, intcount, String str){

this();

this.isWord = isWord;

this.count = count;

this.str = str;

}

publicvoidaddChild(String key, Node node){

childs.put(key, node);

node.parent = this;

}

publicvoidremoveChild(String key){

childs.remove(key);

}

publicString toString(){

return"str : "+ str + ", isWord : "+ isWord + ", count : "+ count;

}

}

// 字典树根节点

privateNode root;

DictionaryTree() {

// 初始化root

root = newNode();

}

// 添加字串

privatevoidaddStr(String word, Node node){

// 计数

node.count++;

String str = node.str;

ifnull!= str) {

// 寻找公共前缀

String commonPrefix = "";

forinti= 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()) {

// 与之前的词重复

elseif(commonPrefix.length() == str.length() && commonPrefix.length() < word.length()) {

// 剩余的串

String wordLeft = word.substring(commonPrefix.length());

// 剩余的串去子节点中继续找

searchChild(wordLeft, node);

elseif(commonPrefix.length() < str.length()) {

// 节点裂变

Node splitNode = newNode( 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 = newNode( true1, wordLeft);

splitNode.addChild(wordLeft, leftNode);

}

}

else{

// 没有共同前缀,直接添加节点

Node newNode = newNode( true1, word);

node.addChild(word, newNode);

}

else{

// 根结点

if(node.childs.size() > 0) {

searchChild(word, node);

else{

Node newNode = newNode( true1, word);

node.addChild(word, newNode);

}

}

}

// 在子节点中添加字串

publicvoidsearchChild(String wordLeft, Node node){

booleanisFind = 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 = newNode( true1, wordLeft);

node.addChild(wordLeft, newNode);

}

}

// 添加单词

publicvoidadd(String word){

addStr(word, root);

}

// 在节点中查找字串

privatebooleanfindStr(String word, Node node){

booleanisMatch = true;

String wordLeft = word;

String str = node.str;

ifnull!= 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);

booleanisChildFind = findStr(wordLeft, childNode);

if(isChildFind) {

returntrue;

}

}

returnfalse;

else{

// 没有剩余单词长度,说明已经匹配完毕,直接返回节点是否为单词

returnnode.isWord;

}

}

returnfalse;

}

// 查找单词

publicbooleanfind(String word){

returnfindStr(word, root);

}

// 统计子节点字串单词数

privateintcountChildStr(String prefix, Node node){

// 遍历孩子

for(String key : node.childs.keySet()) {

Node childNode = node.childs.get(key);

// 匹配子节点

intchildCount = countStr(prefix, childNode);

if(childCount != 0) {

returnchildCount;

}

}

return0;

}

// 统计字串单词数

privateintcountStr(String prefix, Node node){

String str = node.str;

// 非根结点

ifnull!= str) {

// 前缀与字串不匹配

if(prefix.indexOf(str) != 0&& str.indexOf(prefix) != 0) {

return0;

// 前缀匹配字串,且前缀较短

elseif(str.indexOf(prefix) == 0) {

// 找到目标节点,返回单词数

returnnode.count;

// 前缀匹配字串,且字串较短

elseif(prefix.indexOf(str) == 0) {

// 剩余字串继续匹配子节点

String prefixLeft = prefix.substring(str.length());

if(prefixLeft.length() > 0) {

returncountChildStr(prefixLeft, node);

}

}

else{

// 根结点,直接找其子孙

returncountChildStr(prefix, node);

}

return0;

}

// 统计前缀单词数

publicintcount(String prefix){

// 处理特殊情况

ifnull== prefix || prefix.trim().isEmpty()) {

returnroot.count;

}

// 从根结点往下匹配

returncountStr(prefix, root);

}

// 打印节点

privatevoidprintNode(Node node, intlayer){

// 层级递进

forinti= 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);

}

}

// 打印字典树

publicvoidprint(){

printNode(root, 0);

}

}

(友情提示:可左右滑动)

Main.java

/**

* @author xiaoshi on 2018/10/5.

*/

publicclassMain{

publicstaticvoidmain(String[] args{

DictionaryTree dt = newDictionaryTree();

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);

intcount = 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控件是不是就可以用?


相关推荐