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

这题当时用List做的，就是遍历，复杂度O(m * n)，m是单词长度，n是词典大小，也AC了但是LEETCODE提到了数据量大的情况。
我看了一下别人用Map做的，复杂度O(m + n)。
定义了一个Map<String , int []>；
用这样的技巧：
String key = s.substring(0, i) + s.substring(i + 1);
substring的第一个参数是inclusive的，第二个是exclusive的。

对于hello这样的String，存放着诸如helo->{[2,'o'], [3,'o']}这样的键值对。

 List<int[]> val = map.getOrDefault(key, new ArrayList<int[]>());
 val.add(pair);

上面这段的意思是把这个map的value弄成一个entry样式的，一个key对应一个包含好几个pari的list，每个pair保存着第几位去掉了哪个字母。真晦涩啊。

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 s : dict) {
            for (int i = 0; i < s.length(); i++) {
                String key = s.substring(0, i) + s.substring(i + 1);
                int[] pair = new int[] {i, s.charAt(i)};
                
                List<int[]> val = map.getOrDefault(key, new ArrayList<int[]>());
                val.add(pair);
                
                map.put(key, val);
            }
        }
    }
    
    /** 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[] pair : map.get(key)) {
                    if (pair[0] == i && pair[1] != word.charAt(i)) return true;
                }
            }
        }
        return false;
    }
}