如何在500w个单词中统计特定前缀的单词有多少个?

面试现场 0 1.4K

如何在500w个单词中统计特定前缀的单词有多少个？

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

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

题目：我有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控件是不是就可以用？

算法面试面试现场

发表评论取消回复

后才能评论

Stan 游客 2022-01-20 9:31 下午

没有文章中的那么麻烦吧

登录以回复
Stan 游客 2022-01-20 9:30 下午

class Solution {
public String longestPalindrome(String s) {
if (s null || s.length() < 1) { return “”;}
int begin = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// 不同的中心点
int length1 = this.findFromCenter(s, i, i);
int length2 = this.findFromCenter(s, i, i + 1);
int len = Math.max(length1, length2);
if (len > end – begin) {
begin = i – (len – 1) / 2;
end = i + len / 2;
}
}
return s.substring(begin, end + 1);
}

private int findFromCenter(String str, int left, int right) { int newL = left; int newR = right; while (newL >= 0 && newR < str.length() && str.charAt(newL) == str.charAt(newR)) { newL--; newR++; } return newR - newL - 1; } }

登录以回复

发表评论 取消回复

评论(2)

发表评论取消回复