676. Implement Magic Dictionary

676. Implement Magic Dictionary

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.

My Solutions:

方法1：最naive的方法就是先建立字典，build时直接把每一个词加入字典。search时把需要search的word的每一种可能的组合都试一遍

//pseudo code

List<String> words = new ArrayList<>();

public void build(String[] dict) {
    for (String s : dict) words.add(s);
}

public boolean search(String word) {
    for (String s : words) {
        if (word.length() != s.length()) continue;
        int count = 0;
        for (int i = 0; i < word.length(); i++) {
            char a = word.charAt(i);
            char b = word.charAt(i);
            if (a != b) count++;
            if (count > 1) break;
        }
        if (count == 1) return true;
    }
    return false;
}

方法2：建立一个map， key是每一个单词去掉一个字母，e.g. hello 的key是ello, helo, hllo，对应的value是a list of int[] data, 里面装着去掉的字母的index和此字母的unicode。e.g. key是helo，value是{[2, 'l'], [3, 'l']}。这样在search时，word进行同样的处理，去掉一个字母，再在map里找相同的key，检查value里是否有相同index，但char不同的情况。如果有，则返回true

class MagicDictionary {

    Map<String, List<int[]>> map = new HashMap<>();
    
    /** Initialize your data structure here. */
    public MagicDictionary() {
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String str : dict) {
            for (int i = 0; i < str.length(); i++) {
                String key = str.substring(0, i) + str.substring(i + 1); //e.g. key = "helo";
                int[] data = new int[]{i, str.charAt(i)}; //e.g. {2, "l"} & {3, "l"}
                List<int[]> value = map.getOrDefault(key, new ArrayList<int[]>());
                value.add(data);
                map.put(key, value);             
            }
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    public boolean search(String word) {
        for (int i = 0; i < word.length(); i++) {
            String key = word.substring(0, i) + word.substring(i + 1);
            if (map.containsKey(key)) {
                for (int[] data : map.get(key)) {
                    if (i == data[0] && word.charAt(i) != data[1]) return true;
                }
            }
        }
        return false;
    }
}