iis服务器助手广告广告
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++实现LeetCode之神奇字典的示例分析
  • 572
分享到

C++实现LeetCode之神奇字典的示例分析

2023-06-20 20:06:04 572人浏览 泡泡鱼
摘要

这篇文章将为大家详细讲解有关c++实现LeetCode之神奇字典的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。[LeetCode] 676.Implement Magic Dictionary

这篇文章将为大家详细讲解有关c++实现LeetCode之神奇字典的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

[LeetCode] 676.Implement Magic Dictionary 实现神奇字典

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you'll be given a list of non-repetitive Words to build a dictionary.

For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Note:

  1. You may assume that all the inputs are consist of lowercase letters a-z.

  2. For contest purpose, the test data is rather small by now. You could think about highly efficient alGorithm after the contest.

  3. Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

这道题让我们设计一种神奇字典的数据结构,里面有一些单词,实现的功能是当我们搜索一个单词,只有存在和这个单词只有一个位置上的字符不相同的才能返回true,否则就返回false,注意完全相同也是返回false,必须要有一个字符不同。博主首先想到了One Edit Distance那道题,只不过这道题的两个单词之间长度必须相等。所以只需检测和要搜索单词长度一样的单词即可,所以我们用的数据结构就是根据单词的长度来分,把长度相同相同的单词放到一起,这样就可以减少搜索量。那么对于和要搜索单词进行比较的单词,由于已经保证了长度相等,我们直接进行逐个字符比较即可,用cnt表示不同字符的个数,初始化为0。如果当前遍历到的字符相等,则continue;如果当前遍历到的字符不相同,并且此时cnt已经为1了,则break,否则cnt就自增1。退出循环后,我们检测是否所有字符都比较完了且cnt为1,是的话则返回true,否则就是跟下一个词比较。如果所有词都比较完了,则返回false,参见代码如下:

解法一:

class MagicDictionary {public:        MagicDictionary() {}            void buildDict(vector<string> dict) {        for (string word : dict) {            m[word.size()].push_back(word);        }    }            bool search(string word) {        for (string str : m[word.size()]) {            int cnt = 0, i = 0;            for (; i < word.size(); ++i) {                if (word[i] == str[i]) continue;                if (word[i] != str[i] && cnt == 1) break;                 ++cnt;            }            if (i == word.size() && cnt == 1) return true;        }        return false;    }private:    unordered_map<int, vector<string>> m;};

下面这种解法实际上是用到了前缀树中的search的思路,但是我们又没有整个用到prefix tree,博主感觉那样写法略复杂,其实我们只需要借鉴一下search方法就行了。我们首先将所有的单词都放到一个集合中,然后在search函数中,我们遍历要搜索的单词的每个字符,然后把每个字符都用a-z中的字符替换一下,形成一个新词,当然遇到本身要跳过。然后在集合中看是否存在,存在的话就返回true。记得换完一圈字符后要换回去,不然就不满足只改变一个字符的条件了,参见代码如下:

解法二:

class MagicDictionary {public:        MagicDictionary() {}            void buildDict(vector<string> dict) {        for (string word : dict) s.insert(word);    }            bool search(string word) {        for (int i = 0; i < word.size(); ++i) {            char t = word[i];            for (char c = 'a'; c <= 'z'; ++c) {                if (c == t) continue;                word[i] = c;                if (s.count(word)) return true;            }            word[i] = t;        }        return false;    }    private:    unordered_set<string> s;};

关于“C++实现LeetCode之神奇字典的示例分析”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

--结束END--

本文标题: C++实现LeetCode之神奇字典的示例分析

本文链接: https://www.lsjlt.com/news/300052.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • C++实现LeetCode之神奇字典的示例分析
    这篇文章将为大家详细讲解有关C++实现LeetCode之神奇字典的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。[LeetCode] 676.Implement Magic Dictionary ...
    99+
    2023-06-20
  • C++实现LeetCode(676.实现神奇字典)
    [LeetCode] 676.Implement Magic Dictionary 实现神奇字典 Implement a magic directory with buil...
    99+
    2024-04-02
  • C++实现LeetCode之区间的示例分析
    这篇文章将为大家详细讲解有关C++实现LeetCode之区间的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。[LeetCode] 228.Summary Ranges 总结区间Given a so...
    99+
    2023-06-20
  • C++实现LeetCode的示例分析
    这篇文章主要介绍C++实现LeetCode的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!Reverse a linked list from position m to n. ...
    99+
    2023-06-20
  • C++实现LeetCode之缺失区间的示例分析
    这篇文章给大家分享的是有关C++实现LeetCode之缺失区间的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。[LeetCode] 163. Missing Ranges 缺失区间Given a sort...
    99+
    2023-06-20
  • C++实现LeetCode之包围区域的示例分析
    这篇文章将为大家详细讲解有关C++实现LeetCode之包围区域的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。[LeetCode] 130. Surrounded Regions 包围区域Giv...
    99+
    2023-06-20
  • C++实现LeetCode之岛屿数量的示例分析
    这篇文章主要为大家展示了“C++实现LeetCode之岛屿数量的示例分析”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“C++实现LeetCode之岛屿数量的示例分析”这篇文章吧。[LeetCod...
    99+
    2023-06-20
  • C++实现LeetCode之版本比较的示例分析
    小编给大家分享一下C++实现LeetCode之版本比较的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧![LeetCode] 165.Compare Ver...
    99+
    2023-06-20
  • C++实现LeetCode之替换单词的示例分析
    这篇文章主要介绍C++实现LeetCode之替换单词的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完![LeetCode] 648.Replace Words 替换单词In English, we have a...
    99+
    2023-06-20
  • C++中LeetCode实现单独数字的示例分析
    这篇文章主要介绍了C++中LeetCode实现单独数字的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。[LeetCode] 136.Single Number 单独的...
    99+
    2023-06-20
  • C++实现LeetCode之求最大间距的示例分析
    这篇文章主要介绍C++实现LeetCode之求最大间距的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完![LeetCode] 164. Maximum Gap 求最大间距Given an unsorted ar...
    99+
    2023-06-20
  • C++实现LeetCode之加油站问题的示例分析
    这篇文章主要介绍C++实现LeetCode之加油站问题的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完![LeetCode] 134.Gas Station 加油站问题There are N ...
    99+
    2023-06-20
  • C++实现LeetCode之前K个高频词的示例分析
    这篇文章主要介绍了C++实现LeetCode之前K个高频词的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。[LeetCode] 692.Top K Frequent ...
    99+
    2023-06-20
  • C++实现LeetCode之前K个高频元素的示例分析
    这篇文章主要为大家展示了“C++实现LeetCode之前K个高频元素的示例分析”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“C++实现LeetCode之前K个高频元素的示例分析”这篇文章吧。[L...
    99+
    2023-06-20
  • C++实现LeetCode之添加和查找单词的示例分析
    这篇文章将为大家详细讲解有关C++实现LeetCode之添加和查找单词的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。[LeetCode] 211.Add and Search Word - Da...
    99+
    2023-06-20
  • C++实现LeetCode之最短子数组求和的示例分析
    这篇文章主要介绍C++实现LeetCode之最短子数组求和的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完![LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和Gi...
    99+
    2023-06-20
  • C++使用LeetCode实现二叉搜索树的示例分析
    这篇文章将为大家详细讲解有关C++使用LeetCode实现二叉搜索树的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。Given an integer n, generate all st...
    99+
    2023-06-20
  • C/C++经典算法之约瑟夫问题的示例分析
    这篇文章给大家分享的是有关C/C++经典算法之约瑟夫问题的示例分析的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。什么是约瑟夫问题? 约瑟夫问题:n个人围成一圈,初始编号从1~n排列,从约定编号为x的人开...
    99+
    2023-06-20
  • leetcode链表之分割链表的示例分析
    这篇文章主要介绍了leetcode链表之分割链表的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。题目编写程序以 x 为基准分割链表,使得所有小于&...
    99+
    2023-06-19
  • Python字典查找性能的示例分析
    这期内容当中小编将会给大家带来有关Python字典查找性能的示例分析,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。timeit.repeattimeit.repeat默认会执行3轮,每轮执行1000000...
    99+
    2023-06-22
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作