Implement Magic Dictionary

https://leetcode.com/problems/implement-magic-dictionary/description/

Implement a magic directory withbuildDict, andsearchmethods.

For the methodbuildDict, you'll be given a list of non-repetitive words to build a dictionary.

For the methodsearch, you'll be given a word, and judge whether if you modifyexactlyone character intoanothercharacter in this word, the modified word is in the dictionary you just built.

Thoughts

brute-force是对给定的str和dict中的每个string作比较. 想到可以把每个在dict的字符串的每一位删除所形成的新字符串放入一个set中。对给定的字符串依次删除字符，当剩下的字符组成的字符串出现在了set中，即返回true.

但这么做有个问题，即如果给定一个在dict中的字符串时，它也返回true. 所以又创建了一个oriSet记录dict中的字符串，如果给定的match其中一个，直接返回。

可还是有问题，因为即使和oriSet 的match并不意味着给定的string 就是不能通过修改dict中另一个string的某位得来。比如dict中放入[hello, hallo] 现在给hello, 虽然oriSet包含了hello, 但hello可以由hallo修改一个字符得到. 现在问题变得复杂, 逻辑不大好理清了.

也就是我们要对每个在dict中的每个string在和给定str不同的情况下, 判断是否可以通过删除string和str某字符后match. 但这样又是一一比较, 时间复杂度高.

后来看到大神的解法, 想法其实很接近了, 依然是把所有可能的删除一个字符后形成的substring放入, 不过是放入map中. 然后每个substring维护一个set, 记录下是由谁 在什么位置上 放的. 对给定的str, 依然是依次删除一个字符形成新的字符串, 然后和map中匹配, 如果匹配成功再继续遍历sub对应的set, 看是否存在和str不同的放入者.

Code

class MagicDictionary {
    Map<String, Map<Integer, Set<String>>> map;

    /** Initialize your data structure here. */
    public MagicDictionary() {
        map = new HashMap<>();
    }

    /** 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++) {
                StringBuilder sb = new StringBuilder(str);
                String sub = sb.deleteCharAt(i).toString();
                if (!map.containsKey(sub)) {
                    map.put(sub, new HashMap<>());
                }
                if (!map.get(sub).containsKey(i)) {
                    map.get(sub).put(i, new HashSet<>());
                }
                map.get(sub).get(i).add(str);
            }
        }
    }

    /** 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++) {
            StringBuilder sb = new StringBuilder(word);
            String sub = sb.deleteCharAt(i).toString();
            if (map.containsKey(sub) && map.get(sub).containsKey(i)) {
                if (!map.get(sub).get(i).contains(word) || map.get(sub).get(i).size() > 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dict);
 * boolean param_2 = obj.search(word);
 */

Analysis

Errors: 1. 如thoughts所说. 2. 位置也很重要, 比如[ab]和[ba] 两者删除a后相同, 但对ab只修改一个字符无法变成ba.

search时间复杂度为字符串长度. 空间复杂度为dict长度*每个string长度.