676 Implement Magic Dictionary 實(shí)現(xiàn)一個(gè)魔法字典
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.
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
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.
題目描述:
設(shè)計(jì)一個(gè)使用單詞列表進(jìn)行初始化的數(shù)據(jù)結(jié)構(gòu)枚碗，單詞列表中的單詞 互不相同 。 如果給出一個(gè)單詞，請(qǐng)判定能否只將這個(gè)單詞中一個(gè)字母換成另一個(gè)字母奈籽，使得所形成的新單詞存在于你構(gòu)建的字典中前硫。
實(shí)現(xiàn) MagicDictionary 類：
MagicDictionary() 初始化對(duì)象
void buildDict(String[] dictionary) 使用字符串?dāng)?shù)組 dictionary 設(shè)定該數(shù)據(jù)結(jié)構(gòu)，dictionary 中的字符串互不相同
bool search(String searchWord) 給定一個(gè)字符串 searchWord ，判定能否只將字符串中 一個(gè) 字母換成另一個(gè)字母副编，使得所形成的新字符串能夠與字典中的任一字符串匹配扣典。如果可以妆毕，返回 true ；否則贮尖，返回 false 笛粘。
示例 :
輸入
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
輸出
[null, null, false, true, false, false]
解釋
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["hello", "leetcode"]);
magicDictionary.search("hello"); // 返回 False
magicDictionary.search("hhllo"); // 將第二個(gè) 'h' 替換為 'e' 可以匹配 "hello" ，所以返回 True
magicDictionary.search("hell"); // 返回 False
magicDictionary.search("leetcoded"); // 返回 False
提示:
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
dictionary[i] 僅由小寫英文字母組成
dictionary 中的所有字符串 互不相同
1 <= searchWord.length <= 100
searchWord 僅由小寫英文字母組成
buildDict 僅在 search 之前調(diào)用一次
最多調(diào)用 100 次 search
思路:
- 暴力法
按照單詞的不同長(zhǎng)度將單詞放到哈希表中
搜索時(shí)遍歷哈希表, 找到只有 1 個(gè)不同的字母的單詞
build() 時(shí)間復(fù)雜度 O(s), search() 時(shí)間復(fù)雜度 O(mn), 空間復(fù)雜度 O(s), 其中 s 為所有單詞字母總數(shù), n 為魔法字典單詞數(shù), m 為搜索單詞的長(zhǎng)度 - 前綴樹
build() 時(shí)間復(fù)雜度 O(s), search() 時(shí)間復(fù)雜度 O(mn), 空間復(fù)雜度 O(s), 其中 s 為所有單詞字母總數(shù), n 為魔法字典單詞數(shù), m 為搜索單詞的長(zhǎng)度 - 替代法
將單詞的每一個(gè)字母用 '' 代替之后存入哈希表
搜索時(shí)搜索長(zhǎng)度相同的哈希表中的單詞, 同樣將待搜索單詞的每一個(gè)字母替換成 ''
搜索匹配且搜索單詞不在哈希表中
build() 時(shí)間復(fù)雜度 O(s ^ 2), search() 時(shí)間復(fù)雜度 O(mn), 空間復(fù)雜度 O(s ^ 2), 其中 s 為單詞字母數(shù), n 為魔法字典單詞數(shù), m 為搜索單詞的長(zhǎng)度
代碼:
C++:
class Trie
{
public:
bool is_word;
vector<Trie*> children;
Trie() : is_word(false), children(26, nullptr) {};
~Trie()
{
for (Trie* child : children) if (child) delete child;
}
};
class MagicDictionary
{
private:
Trie *root;
void add(string &word)
{
Trie *cur = root;
for (auto c : word)
{
if (!cur -> children[c - 'a']) cur -> children[c - 'a'] = new Trie();
cur = cur -> children[c - 'a'];
}
cur -> is_word = true;
}
bool helper(Trie *cur, string &word, int start, bool changed)
{
if (!cur) return false;
if (start == word.size()) return changed and cur -> is_word;
else
{
for (int i = 0; i < 26; i++)
{
if (cur -> children[i])
{
if ('a' + i == word[start])
{
if (helper(cur -> children[i], word, start + 1, changed)) return true;
}
else if (!changed and (helper(cur -> children[i], word, start + 1, true))) return true;
}
}
}
return false;
}
public:
/** Initialize your data structure here. */
MagicDictionary()
{
root = new Trie();
}
void buildDict(vector<string> dictionary)
{
for (auto &word : dictionary) add(word);
}
bool search(string searchWord)
{
return helper(root, searchWord, 0, false);
}
};
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary* obj = new MagicDictionary();
* obj->buildDict(dictionary);
* bool param_2 = obj->search(searchWord);
*/
Java:
class MagicDictionary {
private Map<Integer, List<String>> map;
/** Initialize your data structure here. */
public MagicDictionary() {
map = new HashMap<Integer, List<String>>();
}
public void buildDict(String[] dictionary) {
for (String word : dictionary) {
if (map.containsKey(word.length())) map.get(word.length()).add(word);
else {
List<String> list = new ArrayList<>();
list.add(word);
map.put(word.length(), list);
}
}
}
public boolean search(String searchWord) {
for (String word : map.getOrDefault(searchWord.length(), new ArrayList<String>())) {
int cur = 0;
for (int i = 0; i < searchWord.length(); i++) if (word.charAt(i) != searchWord.charAt(i)) ++cur;
if (cur == 1) return true;
}
return false;
}
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary obj = new MagicDictionary();
* obj.buildDict(dictionary);
* boolean param_2 = obj.search(searchWord);
*/
Python:
class MagicDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
self.d = defaultdict(set)
def buildDict(self, dictionary: List[str]) -> None:
for word in dictionary:
self.d[len(word)].add(word)
def search(self, searchWord: str) -> bool:
return any(sum(word[i] != searchWord[i] for i in range(len(searchWord))) == 1 for word in self.d[len(searchWord)])
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dictionary)
# param_2 = obj.search(searchWord)
