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: 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:
    /** Initialize your data structure here. */
    MagicDictionary() {}

    /** Build a dictionary through a list of words */
    void buildDict(vector<string> 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_map<int, vector<string>> m;
};

下面这种解法实际上是用到了前缀树中的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<string> 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<string> 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++实现实现神奇字典内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(208.实现字典树(前缀树))

    [LeetCode] 208. Implement Trie (Prefix Tree) 实现字典树(前缀树) Implement a trie with insert, search, and startsWith methods. Example: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple");   // returns true trie.search("app&

  • C++实现LeetCode(207.课程清单)

    [LeetCode] 207. Course Schedule 课程清单 There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given

  • C++实现LeetCode(648.替换单词)

    [LeetCode] 648.Replace Words 替换单词 In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another w

  • C++实现LeetCode(202.快乐数)

    [LeetCode] 202.Happy Number 快乐数 Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits,

  • C++实现LeetCode(203.移除链表元素)

    [LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits

  • C++实现LeetCode(211.添加和查找单词-数据结构设计)

    [LeetCode] 211.Add and Search Word - Data structure design 添加和查找单词-数据结构设计 Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string c

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

    [LeetCode] 642. Design Search Autocomplete System 设计搜索自动补全系统 Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you ne

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • 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

  • 一波神奇的Python语句、函数与方法的使用技巧总结

    一波神奇的Python语句、函数与方法的使用技巧总结

    显示有限的接口到外部 当发布python第三方package时,并不希望代码中所有的函数或者class可以被外部import,在__init__.py中添加__all__属性,该list中填写可以import的类或者函数名, 可以起到限制的import的作用, 防止外部import其他函数或者类. #!/usr/bin/env python # -*- coding: utf-8 -*- from base import APIBase from client import Client fro

  • Python神奇的内置函数locals的实例讲解

    摘要 本文我们介绍神奇的locals函数,包括动态创建变量和动态访问变量,以及一个应用场景. 相同属性不相邻问题 需求:有两个list,分别为list1和list2.list1中有n个对象,每个对象有5个属性,其中一个属性是tid,要求list1按tid排序,相邻的对象的tid不能重复,m为不重复的tid数量,m不确定.list2存放的是所有可能出现的tid的情况. list1 = [task1,task2,task3-taskn] list2 = [tid1,tid2,tid3-tidm] (

  • 浅谈Python 列表字典赋值的陷阱

    今天在用python刷leetcode 3Sum problem时,调入到了一个大坑中,检查半天并没有任何逻辑错误,但输出结果却总是不对,最终通过调试发现原来python中list和dict类型直接赋值竟然是浅拷贝!!!因此,在实际实验中,若要实现深拷贝,建立新list或dict,使新建的list或dict变量和以前的变量只是具有相同的值,但是却具有不同的存储地址,保证在改变以前的list变量的时候,不会对新的list产生任何影响. python中的深拷贝的实现需要通过copy.deepcopy

  • C++实现LeetCode(5.最长回文子串)

    [LeetCode] 5. Longest Palindromic Substring 最长回文子串 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is als

  • C++实现LeetCode(44.外卡匹配)

    [LeetCode] 44. Wildcard Matching 外卡匹配 Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequenc

  • C++实现LeetCode(17.电话号码的字母组合)

    [LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合 Given a string containing digits from 2-9inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone butt

  • C++实现LeetCode(139.拆分词句)

    [LeetCode] 139. Word Break 拆分词句 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dic

  • C++实现LeetCode(127.词语阶梯)

    [LeetCode] 127.Word Ladder 词语阶梯 Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transforme

随机推荐