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 stringsdictionary.bool search(String searchWord)Returnstrueif you can change exactly one character insearchWordto match any string in the data structure, otherwise returnsfalse.
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 <= 1001 <= dictionary[i].length <= 100dictionary[i]consists of only lower-case English letters.- All the strings in
dictionaryare distinct. 1 <= searchWord.length <= 100searchWordconsists of only lower-case English letters.buildDictwill be called only once beforesearch.- At most
100calls will be made tosearch.
class MagicDictionary:
def __init__(self):
self.d = None
def buildDict(self, dictionary: List[str]) -> None:
self.d = dictionary
def search(self, searchWord: str) -> bool:
for w in self.d:
if len(w) != len(searchWord):
continue
diff = sum(a != b for a, b in zip(w, searchWord))
if diff == 1:
return True
return False
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dictionary)
# param_2 = obj.search(searchWord)class MagicDictionary:
def __init__(self):
"""
Initialize your data structure here.
"""
def gen(self, word):
return [word[:i] + '*' + word[i + 1:] for i in range(len(word))]
def buildDict(self, dictionary: List[str]) -> None:
self.s = set(dictionary)
self.cnt = Counter(p for word in dictionary for p in self.gen(word))
def search(self, searchWord: str) -> bool:
for p in self.gen(searchWord):
if self.cnt[p] > 1 or (self.cnt[p] == 1 and searchWord not in self.s):
return True
return False
# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dictionary)
# param_2 = obj.search(searchWord)class MagicDictionary {
private String[] d;
public MagicDictionary() {
}
public void buildDict(String[] dictionary) {
d = dictionary;
}
public boolean search(String searchWord) {
for (String w : d) {
if (w.length() != searchWord.length()) {
continue;
}
int diff = 0;
for (int i = 0; i < w.length(); ++i) {
if (w.charAt(i) != searchWord.charAt(i)) {
++diff;
}
}
if (diff == 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);
*/class MagicDictionary {
private Set<String> s = new HashSet<>();
private Map<String, Integer> cnt = new HashMap<>();
/** Initialize your data structure here. */
public MagicDictionary() {
}
public void buildDict(String[] dictionary) {
for (String word : dictionary) {
s.add(word);
for (String p : gen(word)) {
cnt.put(p, cnt.getOrDefault(p, 0) + 1);
}
}
}
public boolean search(String searchWord) {
for (String p : gen(searchWord)) {
int v = cnt.getOrDefault(p, 0);
if (v > 1 || (v == 1 && !s.contains(searchWord))) {
return true;
}
}
return false;
}
private List<String> gen(String word) {
List<String> res = new ArrayList<>();
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length; ++i) {
char c = chars[i];
chars[i] = '*';
res.add(new String(chars));
chars[i] = c;
}
return res;
}
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary obj = new MagicDictionary();
* obj.buildDict(dictionary);
* boolean param_2 = obj.search(searchWord);
*/class MagicDictionary {
public:
vector<string> d;
MagicDictionary() {
}
void buildDict(vector<string> dictionary) {
d = move(dictionary);
}
bool search(string searchWord) {
for (auto&& w : d)
{
if (w.size() != searchWord.size()) continue;
int diff = 0;
for (int i = 0; i < w.size(); ++i) diff += w[i] != searchWord[i];
if (diff == 1) return true;
}
return false;
}
};
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary* obj = new MagicDictionary();
* obj->buildDict(dictionary);
* bool param_2 = obj->search(searchWord);
*/class MagicDictionary {
public:
/** Initialize your data structure here. */
MagicDictionary() {
}
void buildDict(vector<string> dictionary) {
for (string word : dictionary)
{
s.insert(word);
for (string p : gen(word)) ++cnt[p];
}
}
bool search(string searchWord) {
for (string p : gen(searchWord))
{
if (cnt[p] > 1 || (cnt[p] == 1 && !s.count(searchWord))) return true;
}
return false;
}
private:
unordered_set<string> s;
unordered_map<string, int> cnt;
vector<string> gen(string word) {
vector<string> res;
for (int i = 0; i < word.size(); ++i)
{
char c = word[i];
word[i] = '*';
res.push_back(word);
word[i] = c;
}
return res;
}
};
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary* obj = new MagicDictionary();
* obj->buildDict(dictionary);
* bool param_2 = obj->search(searchWord);
*/type MagicDictionary struct {
d []string
}
func Constructor() MagicDictionary {
return MagicDictionary{[]string{}}
}
func (this *MagicDictionary) BuildDict(dictionary []string) {
this.d = dictionary
}
func (this *MagicDictionary) Search(searchWord string) bool {
for _, w := range this.d {
if len(w) != len(searchWord) {
continue
}
diff := 0
for i := range w {
if w[i] != searchWord[i] {
diff++
}
}
if diff == 1 {
return true
}
}
return false
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* obj := Constructor();
* obj.BuildDict(dictionary);
* param_2 := obj.Search(searchWord);
*/type MagicDictionary struct {
s map[string]bool
cnt map[string]int
}
/** Initialize your data structure here. */
func Constructor() MagicDictionary {
return MagicDictionary{map[string]bool{}, map[string]int{}}
}
func (this *MagicDictionary) BuildDict(dictionary []string) {
for _, word := range dictionary {
this.s[word] = true
for _, p := range gen(word) {
this.cnt[p]++
}
}
}
func (this *MagicDictionary) Search(searchWord string) bool {
for _, p := range gen(searchWord) {
if this.cnt[p] > 1 || (this.cnt[p] == 1 && !this.s[searchWord]) {
return true
}
}
return false
}
func gen(word string) []string {
var res []string
for i := 0; i < len(word); i++ {
res = append(res, word[:i]+"."+word[i+1:])
}
return res
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* obj := Constructor();
* obj.BuildDict(dictionary);
* param_2 := obj.Search(searchWord);
*/