C++实现LeetCode(642.设计搜索自动补全系统)

下面是C++实现LeetCode设计搜索自动补全系统(642题)的完整攻略。

问题描述

实现一个搜索自动补全系统,可以支持以下功能:

  1. 给定一个字符串prefix,返回所有下一个可能的查询已经它们的出现次数,按照次数排列(降序);
  2. 插入一个句子sentence时,插入这个句子的所有前缀。
  3. 输入的所有字符串都只包含小写字母,且长度不会超过1000。

示例:

输入:["AutocompleteSystem","input","input","input","input"]
     [[["i love you","island","iroman","i love leetcode"],[5,3,2,2]],["i"], [" "], ["a"], ["#"]]
输出: [null, ["i love you","island","i love leetcode"],[],["i love you","i love leetcode"],[]]

其中,输入的"#"表示句子已经结束。

解决思路

要解决这个问题,我们可以使用Trie树结构。Trie树是一种多叉树,用于存储一组字符串。

具体地,我们设立一个Trie树节点类,类成员包括当前字符和子节点数组(大小为26)等,然后设计自动补全的类,成员包括Trie树的根节点、当前搜索的字符串、以及保存搜索结果的vector等。

接下来我们简单分析一下自动补全的过程:

插入一个句子sentence时,遍历sentence中的所有前缀,将其放入Trie树中。
给定一个字符串prefix时,对于Trie树中以prefix作为前缀的最后一个节点进行搜索,然后执行DFS遍历从这个节点的所有子节点开始的子树,这样就可以得到所有的可能搜索以及它们的出现次数。

代码实现

下面是代码实现,完整的代码实现请见:https://github.com/huihuimaizi/LeetCode-642-Design-Search-Autocomplete-System。

// Trie节点
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;  // 子节点数组
    int freq;  // 记录当前前缀的出现次数
    bool isEnd;  // 标记是不是字符串结尾

    TrieNode() : freq(0), isEnd(false) {}
};

// Trie树
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const string& s, int freq) {
        TrieNode* node = root;
        for (const char& c : s) {
            if (node->children.count(c) == 0) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->freq += freq;
        node->isEnd = true;
    }

    void dfs(TrieNode* node, string& path, vector<pair<string, int>>& v) {
        if (node->isEnd) {
            v.emplace_back(path, node->freq);
        }
        for (const auto& kv : node->children) {
            path.push_back(kv.first);
            dfs(kv.second, path, v);
            path.pop_back();
        }
    }

    TrieNode* getRoot() const {
        return root;
    }
private:
    TrieNode* root;
};

class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string>& sentences, vector<int>& times) {
        for (int i = 0; i < sentences.size(); ++i) {
            trie.insert(sentences[i], times[i]);
        }
    }

    vector<string> input(char c) {
        if (c == '#') {
            trie.insert(current_str, 1);
            current_str = "";
            return {};
        }
        current_str.push_back(c);
        vector<pair<string, int>> v;
        trie_node = trie_node ? trie_node->children[c] : trie.getRoot();
        if (trie_node) {
            string path;
            dfsForSearch(trie_node, path, v);
        }
        sort(v.begin(), v.end(), [](const auto& p1, const auto& p2) { return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first); });
        vector<string> res;
        for (int i = 0; i < min((int)v.size(), 3); ++i) {
            res.emplace_back(current_str + v[i].first);
        }
        return res;
    }
private:
    Trie trie;  // Trie树
    string current_str;  // 当前搜索的字符串
    TrieNode* trie_node = nullptr;  // 当前搜索的节点

    void dfsForSearch(TrieNode* node, string& path, vector<pair<string, int>>& v) {
        if (node->isEnd) {
            v.emplace_back(path, node->freq);
        }
        for (const auto& kv : node->children) {
            path.push_back(kv.first);
            dfsForSearch(kv.second, path, v);
            path.pop_back();
        }
    }
};

测试案例

下面是两条测试案例:

案例1

输入:

["AutocompleteSystem","input","input","input","input"]
[[["i love you","island","iroman","i love leetcode"],[5,3,2,2]],["i"],[" "],["a"],["#"]]

输出:

[null, ["i love you","island","i love leetcode"],[],["i love you","i love leetcode"],[]]

案例2

输入:

["AutocompleteSystem","input","input","input","input","input","input","input","input","input"]
[[["abc","abbc","aacc","bbcc"],[3,2,1,1]],["b"],["c"],["#"],["b"],["c"],["#"],["a"],["b"],["c"],["#"]]

输出:

[null,[],[],[],["bc"], ["bc"],["b"],["bc","bbcc","abbc"],["bc","bbcc"],["bc","bbcc","abbc","aacc"]]

总结

在这个问题中,Trie树是解决方法的核心。通过将前缀字符串存储在Trie树中,我们可以实现输入时的搜索以及自动补全输出。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++实现LeetCode(642.设计搜索自动补全系统) - Python技术站

(0)
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • C语言模拟掷骰子游戏

    C语言模拟掷骰子游戏攻略 游戏规则 该游戏的规则如下: 玩家选择游戏模式(一次投掷或三次投掷),并输入对应的数字(1或3)。 系统随机生成一个1~6之间的数字,表示掷出的点数。 如果是一次投掷,系统将输出该点数,并提示玩家是否愿意再次投掷。 如果是三次投掷,则继续执行步骤2,直到三次投掷结束。最终输出投掷结果的总和,并提示玩家是否愿意再次投掷。 实现步骤 对…

    C 2023年5月22日
    00
  • js删除数组中某几项的方法总结

    针对”js删除数组中某几项的方法总结”这个主题,可以分为以下几个步骤进行讲解: 1. 删除数组中指定下标的元素 通过JavaScript中数组对象提供的splice方法可以删除数组中指定下标的元素。splice方法会改变原数组,第一个参数为要删除的元素的下标,第二个参数指定要删除的元素数量。 以下是一段示例代码: // 要操作的数组 let arr = [1…

    C 2023年5月22日
    00
  • 详解如何使用openssl创建自签名证书

    下面我将详细讲解如何使用openssl创建自签名证书。 1. 安装openssl 首先需要确保本地已经安装并配置了openssl,可以使用以下命令检查是否已经安装: openssl version 如果已经安装,则会返回openssl版本的信息。 如果没有安装,则需要先安装openssl,具体方法可以根据不同操作系统进行安装。 2. 生成自签名私钥 使用以下…

    C 2023年5月23日
    00
  • php时间函数用法分析

    PHP时间函数用法分析 1. 介绍 在 PHP 编程中,经常需要获取、操作时间。PHP 提供了一系列的时间函数,可以方便地处理日期、时间相关的操作。本文将分析 PHP 时间函数的常见用法,包括获取时间戳、格式化时间、时间计算等。 2. 时间戳 时间戳是指从“格林尼治标准时间 1970 年 1 月 1 日 0 点 0 分 0 秒”到现在所经过的秒数。在 PHP…

    C 2023年5月22日
    00
  • golang实现sql结果集以json格式输出的方法

    对于”golang实现sql结果集以json格式输出的方法”,我会按照以下步骤进行详细讲解: 步骤一:连接数据库 首先,我们需要将Go程序连接到目标数据库,这个过程可以使用第三方的Go包来实现,例如 “github.com/go-sql-driver/mysql” 或 “github.com/lib/pq”。以下是一个使用MySQL数据库的示例: impor…

    C 2023年5月23日
    00
  • C++ 如何用cout输出hex,oct,dec的解决方法

    使用C++中的cout语句输出数字时,默认是以10进制方式输出的,并且不直接支持以16进制和8进制的方式输出。为了输出16进制和8进制的数字,我们需要使用cout的标志控制。 1.输出16进制的数字 要想输出16进制的数字,需要使用cout中的hex控制符,它可以将数字转换为16进制输出。示例代码如下: #include <iostream> u…

    C 2023年5月23日
    00
  • C语言实现简易贪吃蛇游戏的示例代码

    C语言实现简易贪吃蛇游戏的示例代码攻略 一、游戏规则 贪吃蛇游戏是一种经典的休闲游戏。游戏中控制一条“贪吃蛇”在一个有边界的空间中移动,通过吃食物来增长身体长度,同时不能碰到自己的身体或游戏区域的边界,否则游戏结束。 二、C语言实现 以下是一个简易的贪吃蛇游戏C语言实现的示例代码和攻略: 1. 初始化游戏 首先需要在程序中定义游戏区域的大小,以及记录蛇头、蛇…

    C 2023年5月23日
    00
  • C++实现“隐藏实现,开放接口”的方案

    “隐藏实现,开放接口”是一种基于面向对象设计理念的编程思想,可以通过C++语言的特性来实现。下面是如何使用C++实现“隐藏实现,开放接口”的方案攻略。 封装类的实现 封装是实现隐藏实现的核心。我们使用类来封装相关的数据和函数,并将其对外部隐藏,只提供接口给外部访问。下面是一个简单的封装类的例子: class Point { public: Point(int…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部