*Java* my solution with brief explanations (15ms, beats 95%)


  • 10
    E

    For the TrieNode, each node has two fields:

    • a boolean isEnd that stores whether the current character is the end of a word
    • a TrieNode[] array of size 26 that stores its children

    search and startsWith are combined into a helper method search(String str, int type) to save coding.

    class TrieNode {
    boolean isEnd;
    TrieNode[] children;
    
    public TrieNode() {
        isEnd = true;
        children = new TrieNode[26];
    }
    }
    
    public class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(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;
    }
    
    public boolean search(String word) {
        return search(word, 1);
    }
    public boolean startsWith(String prefix) {
        return search(prefix, 2);
    }
    private boolean search(String str, int type) {
        TrieNode current = root;
        int i=-1, L=str.length();
        while(++i<L) {
            int id = str.charAt(i) - 'a';
            if((current=current.children[id]) == null) return false;
        }
        return type==1 ? current.isEnd : true;
    }
    }

  • 0
    E

    What is the down vote for?


  • 0
    F

    It wasn't me, but I'd venture to guess it's for the extra parameter for search(). My solution was almost identical to yours, just returned current from search() and doing the comparisons in the public methods.


  • 0
    A

    First isEnd can be false initially, so you don't have to set it to false every time you create a node. Second you can use a bool value instead of int as search type.


Log in to reply
 

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