【面试现场】如何在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控件是不是就可以用?

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-11-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

go(golang)中的类型转换

在使用 go 这样的强类型语言时,我们常常会遇到类型转换的问题。比如 int 类型转 int64,interface{} 转 struct ,对一种类型取指针、...

994100
来自专栏Fish

归并排序

在课本上学到了归并排序,不过课本上写得有些模糊,所以查了一下,原本对某科已经失去了信心,不过发现某科C语言版的写得还挺好理解,于是就照着自己写了一个。代码可以自...

27570
来自专栏菩提树下的杨过

字符编码-使用c#研究

微软的那个臭屁的JOEL(就是写《JOEL说软件》的那个牛人)曾说:“每一位软件开发人员必须、绝对要至少具备UNICODE与字符集知识(没有任何例外)”,我也常...

20270
来自专栏desperate633

LeetCode 28. Implement strStr()题目分析代码

对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不...

9030
来自专栏潇涧技术专栏

Python Data Structures - C3 Data Structures

参考内容: 1.Problem Solving with Python Chapter 2 Algorithm Analysis Chapter 3 Ba...

7610
来自专栏Coding迪斯尼

使用普拉特解析法解析复杂的算术表达式

19020
来自专栏程序员的碎碎念

Unicode?utf-8?GB2312?

分享一点关于字符编码的来源的知识,是前段时间在廖雪峰老师的python教程里看到的,觉得很通俗易懂,现在复制了过来分享给各位没看过这个教程的朋友们。Unico...

46690
来自专栏分享达人秀

经常被问到的有深度有内涵的数据结构面试题

数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构,这些数据结构...

20390
来自专栏黑泽君的专栏

java基础和面向对象面试题_01

20120
来自专栏逸鹏说道

我为NET狂官方面试题-基础篇

最近帮人过一遍C#基础,出了点题目,有需要的同志拿走 答案不唯一,官方答案只供参考,若有错误欢迎提出~ 答案明天发 面向过程 99乘法表 ? 用循环来输出以...

33490

扫码关注云+社区

领取腾讯云代金券