676. Implement Magic Dictionary

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 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.

Rust Solution

use std::collections::HashMap;

#[derive(Default)]
struct MagicDictionary {
    data: HashMap<Vec<char>, Vec<(char, usize)>>,
}

impl MagicDictionary {
    fn new() -> Self {
        MagicDictionary::default()
    }

    fn build_dict(&mut self, dict: Vec<String>) {
        for s in dict {
            let s: Vec<char> = s.chars().collect();
            let n = s.len();
            for i in 0..n {
                let mut t = vec![];
                for &c in &s[..i] {
                    t.push(c);
                }
                for &c in &s[i + 1..] {
                    t.push(c);
                }
                self.data.entry(t).or_default().push((s[i], i));
            }
        }
    }

    fn search(&self, word: String) -> bool {
        let s: Vec<char> = word.chars().collect();
        let n = s.len();
        for i in 0..n {
            let mut t = vec![];
            for &c in &s[..i] {
                t.push(c);
            }
            for &c in &s[i + 1..] {
                t.push(c);
            }
            if let Some(v) = self.data.get(&t) {
                for &(c, j) in v {
                    if c != s[i] && i == j {
                        return true;
                    }
                }
            }
        }
        false
    }
}

#[test]
fn test() {
    let mut obj = MagicDictionary::new();
    obj.build_dict(vec_string!["hello", "leetcode"]);
    assert_eq!(obj.search("hello".to_string()), false);
    assert_eq!(obj.search("hhllo".to_string()), true);
    assert_eq!(obj.search("hell".to_string()), false);
    assert_eq!(obj.search("leetcoded".to_string()), false);
}

Having problems with this solution? Click here to submit an issue on github.