Java solution that works with UTF-8 words


  • 0
    B

    public class TrieTest {

    @Test
    public void test() {
        Trie trie = new Trie();
        trie.insert("abracadabra");
        trie.insert("abracadabratototo");
        trie.insert("hello");
        trie.insert("溜雖孫");
    
        long start = System.currentTimeMillis();
        assertTrue(trie.startsWith("abra"));
        assertTrue(trie.startsWith("he"));
        assertTrue(trie.startsWith("溜雖"));
        assertFalse(trie.startsWith("zoe"));
        assertTrue(trie.search("hello"));
        assertTrue(trie.search("abracadabra"));
        assertTrue(trie.search("溜雖孫"));
        assertFalse(trie.search("toto"));
        System.err.println(System.currentTimeMillis() - start + " ms");
    }
    
    class TrieNode {
    
        Map<String, TrieNode> map;
    
        String letter;
    
        public TrieNode(String l) {
            map = new HashMap<>();
            letter = l;
        }
    }
    
    public class Trie {
    
        private static final String END_MARK = "*";
    
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode("");
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            if (word == null || "".equals(word)) return;
    
            String letter = String.valueOf(word.charAt(0));
            TrieNode previousNode = root.map.get(letter);
            if (previousNode == null) {
                previousNode = new TrieNode(letter);
                root.map.put(letter, previousNode);
            }
    
            for(int i = 1; i < word.length(); i++) {
                String currentLetter = String.valueOf(word.charAt(i));
                TrieNode node = previousNode.map.get(currentLetter);
                if (node == null) {
                    node = new TrieNode(currentLetter);
                    previousNode.map.put(currentLetter, node);
                }
                previousNode = node;
            }
    
            previousNode.map.put(END_MARK, new TrieNode(END_MARK));
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode node = getPrefix(word);
            return node != null && node.map.get(END_MARK) != null;
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            return getPrefix(prefix) != null;
        }
    
        private TrieNode getPrefix(String word) {
    
            if(word == null || "".equals(word)) return null;
    
            String letter = String.valueOf(word.charAt(0));
            TrieNode next = root.map.get(letter);
            int i = 1;
    
            while(i < word.length() && next != null && !letter.equals(END_MARK)) {
                letter = String.valueOf(word.charAt(i));
                next = next.map.get(letter);
                i++;
            }
    
            return next;
        }
    }
    

    }


Log in to reply
 

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