Java solution with the use of HashMap and HashSet


  • 0
    H

    As many other solutions point out, it's a nice way to treat the sub-string with length n-1 as a key in a map. But the problem is how can we store the pair(index->character). Character is the deleted character, and Index is its position. Suppose index = i, and character = c.
    For example, "hello" has 5 sub-strings(length 4): ello(0->h) hllo(1->e) helo(2->l) helo(3->l) hell(4->o). "hallo" has hllo(1->a). As we can see, both i and c are not unique. So we have to use at least a vector to store one type of them. My solution is that treat index as key, and store all the relevant characters into a set. Map<String, Map<Integer, Set<Character>>>; When judging if is a word meets the requirement.
    First, generate all (n-1)-length sub-string.
    Then, use the sub-string as outside key and i as inside key.
    In order to avoid situation like dict{"hello"} search{"hello"}, we have to add an if to test if the set only has the deleted character.
    So below is my code.
    class MagicDictionary {

    Map<String, Map<Integer, Set<Character>>> map;
    
    /** Initialize your data structure here. */
    public MagicDictionary() {
    	map = new HashMap<>();
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
    	StringBuilder sb = null;
    	for (String word : dict) {
    		for (int i = 0; i < word.length(); i++) {
    			char c = word.charAt(i);
    			sb = new StringBuilder(word);
    			sb.deleteCharAt(i);
    			String newWord = sb.toString();  
    			if (!map.containsKey(newWord)) {
    				map.put(sb.toString(), new HashMap<>());
    			}
    			if (map.get(newWord).get(i) == null) {
    				map.get(newWord).put(i, new HashSet<>());
    			}
    			Set<Character> set = map.get(newWord).get(i);
    			set.add(c);
    			map.get(newWord).put(i, set);
    		}
    	}
    }
    
    /**
     * 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 = null;
    	for (int i = 0; i < word.length(); i++) {
    		char c = word.charAt(i);
    		sb = new StringBuilder(word);
    		sb.deleteCharAt(i);
    		String newWord = sb.toString();
    		Map<Integer, Set<Character>> mapTemp = map.getOrDefault(newWord, null);
    		if (mapTemp != null) {
    			Set<Character> setTemp = mapTemp.getOrDefault(i, null);
    			boolean c1 = setTemp != null;
    			boolean c2 = c1 && setTemp.size() > 1;
    			boolean c3 = c1 && setTemp.size() == 1 && !setTemp.contains(c);
    			if (c2 || c3) {
    				return true;
    			}
    		}
    	}
    	return false;
    }
    

    }


Log in to reply
 

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