mzoe666888

V1

2022/04/22阅读:22主题:兰青

内卷大厂系列《搜索自动补全二连击》

大厂高频算法面试题:《搜索自动补全系列》,搜索自动补全功能很常见,比如用Google、百度等搜索引擎搜内容时,下拉列表会显示匹配内容的结果,如何设计并实现类似的功能呢?,通过两道算法设计题来分析实现流程。

一、搜索自动补全 I

实现一个typeahead功能,给出一个字符串和一个包含若干个单词的字典,返回所有含有这个字符串子串的单词。字典不能被修改,并且这个方法可能被调用多次。

示例一

输入:
dict=["Jason Zhang","James Yu","Li Zhang","Yanxin Shi"]
search("Zhang")
search("James")

输出:
["Jason Zhang","Li Zhang"]
["James Yu"]

示例二

输入:
dict=["San Zhang","Lisi","Li Zhang","Yanxin Shi"]
search("Li")

输出:
["Li Zhang","Lisi"]

系统设计题《自动补全》

1、分析

子串一定连续,子序列不一定连续!

方法一:枚举所有子串,映射子串和原始串的对应关系,一对多关系,准备一个Map,key为子串,value为列表,用来存放原始串列表。时间复杂度O(M*N²),M为字典的长度,N为字符串的长度。

方法二:利用前缀树,前缀树节点的路径用一个Map表示,不知道有多少条路,key为前缀树节点,value为原始串下标列表,采用外挂方式记录每个前缀节点对应的原始串下标列表,也可以在前缀树结构中增加原始串下标列表属性,本题采用外挂方式(一张表记录每个前缀树节点的映射关系,保持前缀树结构最初干净的状态),时间复杂度O(M*N),M为字典的长度,N为字符串的长度。

2、实现

2.1、方法一

class Typeahead {

    // key:子串,value:原始串列表
    Map<String, Set<String>> substrToWordMap;

    public Typeahead(Set<String> dict) {
        this.substrToWordMap = new HashMap<>();
        for (String word : dict) {
            addSubStringToMap(word, substrToWordMap);
        }
    }

    private void addSubStringToMap(String word, Map<String, Set<String>> substrToWordMap) {
        // 枚举所有子串,并添加进substrToWordMap
        for (int start = 0; start < word.length(); start++) {
            for (int end = start; end < word.length(); end++) {
                String substr = word.substring(start, end + 1);
                Set<String> wordSet = substrToWordMap.getOrDefault(substr, new TreeSet());
                wordSet.add(word);
                substrToWordMap.put(substr, wordSet);
            }
        }
    }

    public List<String> search(String str) {
        List<String> resList = new ArrayList<>();
        if (!substrToWordMap.containsKey(str)) {
            return resList;
        }
        Set<String> wordList = substrToWordMap.get(str);
        resList.addAll(wordList);
        return resList;
    }
}

2.2、方法二

class Typeahead {

    private final Trie trie; // 前缀树
    // 外挂方式,某个前缀树节点,不在这个节点内部,key:节点对象,value:记录原始单词的下标列表
    private final HashMap<Node, List<Integer>> nodeToIndexListMap = new HashMap<>();
    private final String[] words; // 字典,dict -> words,通过 List<Integer> 获取 原始单词列表

    public Typeahead(Set<String> dict) {
        this.words = new String[dict.size()];
        // 构建前缀树
        this.trie = new Trie();
        init(dict);
    }

    // 初始化字典
    private void init(Set<String> dict) {
        int index = 0;
        for (String word : dict) {
            if (word == null || word.isEmpty()) {
                continue;
            }
            // 构建字典
            this.words[index] = word;
            for (int i = 0; i < word.length(); i++) {
                String subStr = word.substring(i);
                // 枚举所有开头的子串,添加进前缀树中
                trie.insert(index, subStr);
            }
            index++;
        }
    }

    public List<String> search(String str) {
        List<String> ans = new ArrayList<>();
        List<Integer> indexList = trie.prefix(str);
        for (Integer index : indexList) {
            ans.add(words[index]);
        }
        return ans;
    }

    class Node {
        // 哈希表实现的前缀树路径,一个节点下不知道有多少条路
        // key:path 通往哪条路,value:路径上的节点
        private final HashMap<Integer, Node> nexts;

        public Node() {
            this.nexts = new HashMap<>();
        }
    }

    class Trie {
        private final Node root; // 前缀树根节点

        public Trie() {
            this.root = new Node();
        }

        public void insert(int index, String word) {
            if (word == null || word.isEmpty()) {
                return;
            }
            char[] chs = word.toCharArray();
            Node node = root;
            int path = 0;
            for (int i = 0; i < chs.length; i++) {
                path = chs[i];
                if (!node.nexts.containsKey(path)) {
                    node.nexts.put(path, new Node());
                }
                node = node.nexts.get(path);
                if (!nodeToIndexListMap.containsKey(node)) {
                    nodeToIndexListMap.put(node, new ArrayList<>());
                }
                List<Integer> ans = nodeToIndexListMap.get(node);
                if (!ans.contains(index)) {
                    ans.add(index);
                }
            }
        }

        // 所有加入的子串中,有几个是以pre作为前缀的
        public List<Integer> prefix(String pre) {
            if (pre == null) {
                return new ArrayList<>();
            }
            char[] chs = pre.toCharArray();
            Node node = root;
            int path = 0;
            for (int i = 0; i < chs.length; i++) {
                path = chs[i];
                if (!node.nexts.containsKey(path)) {
                    return new ArrayList<>();
                }
                node = node.nexts.get(path);
            }
            return nodeToIndexListMap.get(node);
        }

    }

}

二、搜索自动补全 II

为搜索引擎设计一个搜索自动完成系统。用户可以输入一个句子(至少一个单词,并以一个特殊的字符'#'结尾)。对于除'#'之外的每个字符,您需要返回与已输入的句子部分前缀相同的前3个历史热门句子。具体规则如下:

一个句子的热度定义为用户输入完全相同句子的次数。 返回的前3个热门句子应该按照热门程度排序(第一个是最热的)。如果几个句子的热度相同,则需要使用ascii代码顺序(先显示较小的一个)。 如果少于3个热门句子,那么就尽可能多地返回。 当输入是一个特殊字符时,它意味着句子结束,在这种情况下,您需要返回一个空列表。 您的工作是实现以下功能:

构造函数:

AutocompleteSystem(String[] sentence, int[] times):这是构造函数。输入是历史数据。句子是由之前输入的句子组成的字符串数组。Times是输入一个句子的相应次数。您的系统应该记录这些历史数据。

现在,用户想要输入一个新句子。下面的函数将提供用户类型的下一个字符:

List input(char c):输入c是用户输入的下一个字符。字符只能是小写字母(“a”到“z”)、空格(“”)或特殊字符(“#”)。另外,前面输入的句子应该记录在系统中。输出将是前3个历史热门句子,它们的前缀与已经输入的句子部分相同。

例子: 操作:AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2]) 系统已经追踪到以下句子及其对应的时间:

"i love you" : 5 times "island" : 3 times "ironman" : 2 times "i love leetcode" : 2 times

现在,用户开始另一个搜索:

操作:输入(“i”) 输出:["i love you", "island","i love leetcode"] 解释: 有四个句子有前缀“i”。其中,《ironman》和《i love leetcode》有着相同的热度。既然“ ” ASCII码为32,“r”ASCII码为114,那么“i love leetcode”应该在“ironman”前面。此外,我们只需要输出前3个热门句子,所以“ironman”将被忽略。

操作:输入(' ') 输出:[“i love you”,“i love leetcode”] 解释: 只有两个句子有前缀“i”。

操作:输入(' a ') 输出:[] 解释: 没有以“i a”为前缀的句子。

操作:输入(“#”) 输出:[] 解释: 用户完成输入后,在系统中将句子“i a”保存为历史句。下面的输入将被计算为新的搜索。

注意:输入的句子总是以字母开头,以“#”结尾,两个单词之间只有一个空格。 要搜索的完整句子不会超过100个。包括历史数据在内的每句话的长度不会超过100句。 在编写测试用例时,即使是字符输入,也请使用双引号而不是单引号。 请记住重置在AutocompleteSystem类中声明的类变量,因为静态/类变量是跨多个测试用例持久化的。详情请点击这里。

Design Search Autocomplete System

1、分析

设计一个搜索自动补全系统,它需要包含如下两个方法:

构造方法: AutocompleteSystem(String[] sentences, int[] times): 输入句子sentences,及其出现次数times

输入方法: List input(char c): 输入字符c可以是26个小写英文字母,也可以是空格,以'#'结尾。返回输入字符前缀对应频率最高的至多3个句子,频率相等时按字典序排列。

上边这么多的内容浓缩下

26个小写英文字母 + 空格 = 总计27个字符

日常经常用到的功能:搜索自动补全,而且谁排在第一位,是有一定规则的。

比如 "abc" = 7次、"abd" = 4次、"abe" = 2次

第一次搜索a,abc排在第一位

第二次搜索ab,还是abc排在第一位

第三次搜索abc,还是abc排在第一位

当输入abd,搜索结果只有abd,必然的

当输入abd#,#代表搜索结束(相当于按回车搜索),abd的次数加1,abd = 5,假如用户又输入了3次,此时abd = 8

当用户搜索输入a时,此时abd应该排在第一位

如果"abc" = 5次,"abe" = 5次,"abz" = 5次,按照字典序决定谁排在第一位,比如现在都是5次,那么输入a时,abc应该排在第一位,其次abe,abz

怎么实现这种功能?

利用前缀树,但构建前缀树的时候需要增加额外信息才能做到这种搜索机制

每个前缀树节点都有一颗有序表,可以加在前缀树中,也可以通过外挂记录

推荐需要保存之前的历史,比如 abc、abk、afz

用户输入a,推荐出来abc、abk、afz

用户又输入b(ab),推荐出来 abc、abk

需要有保存历史的变量:path,只要没遇到#结束字符,历史需要一直留着

path:输入的字符路径拼起来

cur:当前来到哪个前缀节点上

如果遇到'#',path = "abcd#",之前如果没有,则需要加入,并增加词频,如果存在,则更新词频

每个前缀树节点都要保存一份有序列表,当输入完毕后,如果历史存在,需要更新之前路径上的所有节点保存的信息

有序表的作用:如果次数一样,则按照字典序排序

2、实现

class AutocompleteSystem {

    // 前缀树结构
    private class TrieNode {
        private TrieNode father; // 父指针
        private String path; // 形成的路径
        private TrieNode[] nexts; // 前缀树的通用做法,构建路径

        public TrieNode(TrieNode f, String p) {
            this.father = f;
            this.path = p;
            this.nexts = new TrieNode[27]; // a~z 26个英文字母 + 空格' '
        }
    }

    // 先按照单词出现的次数从大到小排序,如果词频相同,按照字典序排序
    private class WordCount implements Comparable<WordCount{
        private String word;
        private int count;

        public WordCount(String w, int c) {
            this.word = w;
            this.count = c;
        }

        public int compareTo(WordCount o) {
            return count != o.count ? (o.count - count) : word.compareTo(o.word);
        }
    }

    // 题目的要求,只输出排名前3的列表
    private final int top = 3;
    private final TrieNode root = new TrieNode(null"");
    // 某个前缀树节点,上面的有序表,不在这个节点内部
    // 外挂
    private final HashMap<TrieNode, TreeSet<WordCount>> nodeRankMap = new HashMap<>();
    // 字符串 "abc"  7次   ->  ("abc", 7)
    private final HashMap<String, WordCount> wordCountMap = new HashMap<>();
    // 形成的路径
    private String path;
    // 当前来到的节点
    private TrieNode cur;

    // ' ' -> 0
    // 'a' -> 1
    // 'b' -> 2
    // ...
    // 'z' -> 26
    //  '`'  a b  .. z
    private int f(char c) {
        return c == ' ' ? 0 : (c - '`');
    }

    public AutocompleteSystem(String[] sentences, int[] times) {
        path = "";
        cur = root;
        for (int i = 0; i < sentences.length; i++) {
            String word = sentences[i];
            int count = times[i];
            WordCount wc = new WordCount(word, count - 1);
            wordCountMap.put(word, wc);
            for (char c : word.toCharArray()) {
                input(c);
            }
            input('#');
        }
    }

    // 之前已经有一些历史了!
    // 当前键入 c 字符
    // 请顺着之前的历史,根据c字符是什么,继续
    // path : 之前键入的字符串整体
    // cur : 当前滑到了前缀树的哪个节点
    public List<String> input(char c) {
        List<String> ans = new ArrayList<>();
        if (c != '#') {
            path += c;
            int i = f(c);
            if (cur.nexts[i] == null) {
                cur.nexts[i] = new TrieNode(cur, path);
            }
            cur = cur.nexts[i];
            if (!nodeRankMap.containsKey(cur)) {
                nodeRankMap.put(cur, new TreeSet<>());
            }
            int k = 0;
            // for循环本身就是根据排序后的顺序来遍历!
            for (WordCount wc : nodeRankMap.get(cur)) {
                if (k == top) {
                    break;
                }
                ans.add(wc.word);
                k++;
            }
        }
        // c = #   path = "abcde"
        // #
        // a b .. #
        if (c == '#' && !path.equals("")) {
            // 真的有一个,有效字符串需要加入!path
            if (!wordCountMap.containsKey(path)) {
                wordCountMap.put(path, new WordCount(path, 0));
            }
            // 有序表内部的小对象,该小对象参与排序的指标数据改变
            // 但是有序表并不会自动刷新
            // 所以,删掉老的,加新的!
            WordCount oldOne = wordCountMap.get(path);
            WordCount newOne = new WordCount(path, oldOne.count + 1);
            while (cur != root) {
                nodeRankMap.get(cur).remove(oldOne);
                nodeRankMap.get(cur).add(newOne);
                cur = cur.father;
            }
            wordCountMap.put(path, newOne);
            path = "";
            // cur 回到头了
        }
        return ans;
    }

}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1