676. Implement Magic Dictionary

1. Description

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.
Implement the MagicDictionary class:

• MagicDictionary() Initializes the object.
• void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
• bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

2. Example

Example 1

Input
[“MagicDictionary”, “buildDict”, “search”, “search”, “search”, “search”]
[[], [[“hello”, “leetcode”]], [“hello”], [“hhllo”], [“hell”], [“leetcoded”]]
Output
[null, null, false, true, false, false]

Explanation
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict([“hello”, “leetcode”]);
magicDictionary.search(“hello”); // return False
magicDictionary.search(“hhllo”); // We can change the second ‘h’ to ‘e’ to match “hello” so we return True
magicDictionary.search(“hell”); // return False
magicDictionary.search(“leetcoded”); // return False

3. Constraints

• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case English letters.
• All the strings in dictionary are distinct.
• 1 <= searchWord.length <= 100
• searchWord consists of only lower-case English letters.
• buildDict will be called only once before search.
• At most 100 calls will be made to search.

4. Solutions

Map

m = i_dictionary.size(), n is times of search, l is the number of strings with same length as search string

Build
Time complexity: O(m)
Space complexity: O(m)
Search
Time complexity: O(nl)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class MagicDictionary {
private:
    map<int, vector<string>> stringsWithLength;

    int countDifferentChars(string& i_str1, string& i_str2) {
        // they have same length
        int result = 0;
        for (int i = 0; i < i_str1.size(); i++) {
            if (i_str1[i] != i_str2[i])
                result++;
        }

        return result;
    }

public:
    /** Initialize your data structure here. */
    MagicDictionary() {}

    void buildDict(vector<string> i_dictionary) {
        for (auto str : i_dictionary) {
            stringsWithLength[str.size()].push_back(str);
        }
    }

    bool search(string i_searchWord) {
        for (int i = 0; i < stringsWithLength[i_searchWord.size()].size(); i++) {
            if (countDifferentChars(stringsWithLength[i_searchWord.size()][i], i_searchWord) == 1)
                return true;
        }

        return false;
    }
};