*Java* 2 easy to understand solutions (trie | HashMap)


  • 1
    E

    #Method with HashMap#

    Store all words of same length into one set map them to their length.

    public class WordDictionary {
    private HashMap<Integer, HashSet<String>> map = new HashMap<>();
    
    public void addWord(String word) {
        int L = word.length();
        if(map.containsKey(L)) {
            map.get(L).add(word);
        }
        else {
            HashSet<String> set = new HashSet<>();
            set.add(word);
            map.put(L, set);
        }
    }
    
    public boolean search(String word) {
        int L = word.length();
        if(!map.containsKey(L)) return false;
        HashSet<String> set = map.get(L);
        for(String str : set) {
            int i = 0, LL = word.length();
            while(i<LL) {
                if(word.charAt(i)!='.' && str.charAt(i)!=word.charAt(i)) break;
                ++i;
            }
            //System.out.println(i +"\t"+ LL);
            if(i==LL && (word.charAt(i-1)=='.' || str.charAt(i-1)==word.charAt(i-1))) return true;
        }
        return false;
    }
    }
    

    #Method with Trie#

    Once you have the cent of using trie, the remaining work would seem not that difficult. For the search method, I recursively check word suffix until exhausted.

    public class WordDictionary {
    
    private static final int R = 26;
    private TrieNode root;
    
    public class TrieNode {
    	private static final int R = 26;
    	
    	private boolean isEnd;
    	private TrieNode[] children;
    	
    	public TrieNode() {
    		isEnd = true;
    		children = new TrieNode[R];
    	}
    }
    
    public WordDictionary() {
    	root = new TrieNode();
    }
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode current = root;
        for(int i=0, L=word.length(); i<L; i++) {
        	int id = word.charAt(i) - 'a';
        	if(current.children[id]==null) {
        		current.children[id] = new TrieNode();
        		current.children[id].isEnd = false;
        	}
        	current = current.children[id];
        }
        current.isEnd = true;
    }
    
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
    	char[] chars = word.toCharArray();
        return search(chars, 0, chars.length, root);
    }
    
    private boolean search(char[] chars, int start, int L, TrieNode root) {
    	if(start>=L) return root.isEnd;
    	char ch = chars[start];
    	if(ch=='.') {
    		for(int i=0; i<R; i++) {
    			if(root.children[i]==null) continue;
    			if(search(chars, start+1, L, root.children[i])) return true;
    		}
    	}
    	else {
    		if(root.children[ch-'a']!=null) 
    			if(search(chars, start+1, L, root.children[ch-'a'])) return true;
    	}
    	return false;
    }
    }

Log in to reply
 

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