[LeetCode] 676.Implement Magic Dictionary 實現(xiàn)神奇字典

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.

這道題讓我們設計一種神奇字典的數(shù)據(jù)結構，里面有一些單詞，實現(xiàn)的功能是當我們搜索一個單詞，只有存在和這個單詞只有一個位置上的字符不相同的才能返回true，否則就返回false，注意完全相同也是返回false，必須要有一個字符不同。博主首先想到了One Edit Distance那道題，只不過這道題的兩個單詞之間長度必須相等。所以只需檢測和要搜索單詞長度一樣的單詞即可，所以我們用的數(shù)據(jù)結構就是根據(jù)單詞的長度來分，把長度相同相同的單詞放到一起，這樣就可以減少搜索量。那么對于和要搜索單詞進行比較的單詞，由于已經(jīng)保證了長度相等，我們直接進行逐個字符比較即可，用cnt表示不同字符的個數(shù)，初始化為0。如果當前遍歷到的字符相等，則continue；如果當前遍歷到的字符不相同，并且此時cnt已經(jīng)為1了，則break，否則cnt就自增1。退出循環(huán)后，我們檢測是否所有字符都比較完了且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函數(shù)中，我們遍歷要搜索的單詞的每個字符，然后把每個字符都用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++實現(xiàn)LeetCode(676.實現(xiàn)神奇字典)的文章就介紹到這了,更多相關C++實現(xiàn)實現(xiàn)神奇字典內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論