C++实现LeetCode(676.实现神奇字典)
[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: NullNote:
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False
- You may assume that all the inputs are consist of lowercase letters a-z.
- For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
- 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.
解法一:
class MagicDictionary {public:/** Initialize your data structure here. */MagicDictionary() {}/** Build a dictionary through a list of words */void buildDict(vector dict) {for (string word : dict) {m[word.size()].push_back(word); }}/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */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_mapm; };
下面这种解法实际上是用到了前缀树中的search的思路,但是我们又没有整个用到prefix tree,博主感觉那样写法略复杂,其实我们只需要借鉴一下search方法就行了。我们首先将所有的单词都放到一个集合中,然后在search函数中,我们遍历要搜索的单词的每个字符,然后把每个字符都用a-z中的字符替换一下,形成一个新词,当然遇到本身要跳过。然后在集合中看是否存在,存在的话就返回true。记得换完一圈字符后要换回去,不然就不满足只改变一个字符的条件了,参见代码如下:
解法二:
class MagicDictionary {public:/** Initialize your data structure here. */MagicDictionary() {}/** Build a dictionary through a list of words */void buildDict(vector dict) {for (string word : dict) s.insert(word); }/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */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 s; };
类似题目:
Implement Trie (Prefix Tree)
参考资料:
https://discuss.leetcode.com/topic/103004/c-clean-code
https://discuss.leetcode.com/topic/102992/easy-14-lines-java-solution-hashmap
【C++实现LeetCode(676.实现神奇字典)】到此这篇关于C++实现LeetCode(676.实现神奇字典)的文章就介绍到这了,更多相关C++实现实现神奇字典内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 孩子不是实现父母欲望的工具——林哈夫
- opencv|opencv C++模板匹配的简单实现
- Node.js中readline模块实现终端输入
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- java中如何实现重建二叉树
- leetcode|leetcode 92. 反转链表 II
- 人脸识别|【人脸识别系列】| 实现自动化妆