Clean concise Java 8 solution


  • 0
    R

    Using Optional from Java 8 to avoid checks for null.

    import java.util.Optional;
    
    class TrieNode {
        TrieNode[] children = new TrieNode['z'-'a'+1];
        boolean leaf = false;
    
        Optional<TrieNode> child(char c) {
            return Optional.ofNullable(children[c-'a']);
        }
        TrieNode getOrCreateChild(char c) {
            if (!child(c).isPresent()) {
                children[c-'a'] = new TrieNode();
            }
            return child(c).get();
        }
    }
    
    public class Trie {
        private TrieNode root = new TrieNode();
    
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.getOrCreateChild(c);
            }
            node.leaf = true;
        }
    
        public boolean search(String word) {
            return find(word).map(n -> n.leaf).orElse(false);
        }
    
        public boolean startsWith(String prefix) {
            return find(prefix).isPresent();
        }
        
        private Optional<TrieNode> find(String prefix) {
            Optional<TrieNode> node = Optional.of(root);
            for (int i = 0; i<prefix.length() && node.isPresent(); i++) {
                node = node.get().child(prefix.charAt(i));
            }
            return node;
        }
    }

Log in to reply
 

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