Easy 14 lines Java solution, HashMap


  • 8
    1. For each word in dict, for each char, remove the char and put the rest of the word as key, a pair of index of the removed char and the char as part of value list into a map. e.g.
      "hello" -> {"ello":[[0, 'h']], "hllo":[[1, 'e']], "helo":[[2, 'l'],[3, 'l']], "hell":[[4, 'o']]}
    2. During search, generate the keys as in step 1. When we see there's pair of same index but different char in the value array, we know the answer is true. e.g.
      "healo" when remove a, key is "helo" and there is a pair [2, 'l'] which has same index but different char. Then the answer is 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 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;
        }
    }
    

  • 0
    A

    Can you explain the question? I don't know the test case:
    Input: search("hello"), Output: False
    Input: search("hhllo"), Output: True

    Did the dictionary modified the input key?


  • 1

    kind of same. Mine just save the edited char into a list

        Map<String, List<Character>> editMap;  
        /** Initialize your data structure here. */
        public MagicDictionary() {
            editMap = new HashMap<>();
        } 
        /** Build a dictionary through a list of words */
        public void buildDict(String[] dict) {
            for (String d : dict) {
                StringBuilder sb = new StringBuilder(d);
                for (int i = 0; i < sb.length(); i++) { 
                    sb.setCharAt(i, '*');
                    List<Character> list = editMap.getOrDefault(sb.toString(), new LinkedList<>());
                    list.add(d.charAt(i));
                    editMap.put(sb.toString(), list);
                    sb.setCharAt(i, d.charAt(i));
                }        
            }
        }  
        /** 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) {
            StringBuilder sb = new StringBuilder(word);
            for (int i = 0; i < sb.length(); i++) {
                sb.setCharAt(i, '*');
                if (editMap.containsKey(sb.toString())) {
                    for (char c : editMap.get(sb.toString())) {
                        if (c != word.charAt(i)) return true;
                    }
                }
                sb.setCharAt(i, word.charAt(i));
            }
            return false;
        }
    

  • 2

    Actually we don't have to store the char list. Below is my solution:

    class MagicDictionary {
    public:
        unordered_map<string, char> map;
    
        void buildDict(vector<string> dict) {
            for (string &word : dict) {
                for (int i = 0; i < word.size(); i++) {
                    string mw = word;
                    mw[i] = '0';
                    if (!map.count(mw))
                        map[mw] = word[i];
                    else if (map[mw] != word[i])
                        map[mw] = 0;
                }
            }
        }
        
        bool search(string word) {
            for (int i = 0; i < word.size(); i++) {
                string mw = word;
                mw[i] = '0';
                if (map.count(mw) && map[mw] != word[i])
                    return true;
            }
            return false;
        }
    };
    

  • 2

    @mzchen Thanks. This method has to be non-repetitive words to build a dictionary.

        Map<String, Character> map;  
        public MagicDictionary() {
            map = new HashMap<>();
        } 
        public void buildDict(String[] dict) {
            for (String d : dict) {
                StringBuilder sb = new StringBuilder(d);
                for (int i = 0; i < sb.length(); i++) { 
                    sb.setCharAt(i, '*');
                    map.put(sb.toString(), map.containsKey(sb.toString())? '*' : d.charAt(i));
                    sb.setCharAt(i, d.charAt(i));
                }     
            }
        }  
        public boolean search(String word) {
            StringBuilder sb = new StringBuilder(word);
            for (int i = 0; i < sb.length(); i++) {
                sb.setCharAt(i, '*');
                if (map.containsKey(sb.toString()) && word.charAt(i) != map.get(sb.toString())) return true;
                sb.setCharAt(i, word.charAt(i));
            }
            return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.