Algorithms
  • Introduction
  • Analysis of Algorithms
  • Numbers
    • Reverse Integer
    • Palindroms
      • Valid Palindrome
    • Prime factor
    • Prime Number
    • Roman to Integer
    • Happy Number
    • p^k
  • Searching
    • Union-Find Algorithms
    • Finding Peak
    • Find Sum in Array
    • Binary Search
      • Find Index Binary Search
      • Sqrt(x)
      • Search in Rotated Sorted Array
      • Guess Number Higher or Lower
      • First Bad Version
      • Find Peak Element
      • Find Minimum in Rotated Sorted Array
      • Find Minimum in Rotated Sorted Array II
      • Search for a Range
      • Closest Binary Search Tree Value
      • Find K Closest Elements
      • Search in a Sorted Array of Unknown Size
      • Pow(x, n)
      • Valid Perfect Square
      • Find Minimum in Rotated Sorted Array II
      • Intersection of Two Arrays
      • Intersection of Two Arrays II
      • Two Sum II - Input array is sorted
      • Find the Duplicate Number
    • Longest Common Prefix
  • Sorting
    • Elementary Sorts
    • Insertion Sort
    • Bubble Sort
    • Mergesort
    • Quicksort
    • Radix Sort
    • Heap Sort
  • Data Structures
    • Array & List
      • Find Pivot Index
      • Largest Number At Least Twice of Others
      • Plus One
      • Diagonal Traverse
      • Spiral Matrix
      • Pascal's Triangle
      • Implement strStr()
      • Add Binary
      • Duplicate Counts
      • Find Duplicates
      • Reverse String
      • Array Partition I
      • Two Sum II - Input array is sorted
      • Remove Element
      • Max Consecutive Ones
      • Minimum Size Subarray Sum
      • Reverse Words in a String
      • Reverse Words in a String III
      • Remove Duplicates from Sorted Array
      • Move Zeroes
      • Rotate Array
      • Rotate Image
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Valid Anagram
      • 3Sum
      • String to Integer (atoi)
      • Count and Say
      • Merge Sorted Array
      • Shuffle an Array
      • Max Area of Island
    • Matrix
    • Stack
      • Valid Parentheses
      • Min Stack
    • Queue
    • Linked List
      • Design Linked List
      • Design Doubly Linked List
      • Find Middle Element
      • Doubly Linked List
      • Cyclic Linked List
      • Linked List Cycle II
      • Find Nth Element from End
      • Remove Nth Node From End of List
      • Add Two Numbers
      • Merge Two Sorted Lists
      • Remove Nth Node From End of List
      • Reverse Linked List
      • Remove Linked List Elements
      • Odd Even Linked List
      • Design Doubly Linked List
      • Flatten a Multilevel Doubly Linked List
      • Rotate List
      • Copy List with Random Pointer
      • Insert into a Cyclic Sorted List
      • Delete Node in a Linked List
      • Palindrome Linked List
    • Set
      • Intersection of Two Arrays
      • Single Number
      • Contains Duplicate
      • Contains Duplicate II
      • Jewels and Stones
      • Longest Substring Without Repeating Characters
      • Two Sum III - Data structure design
      • Valid Sudoku
      • Missing Number
    • Map
      • Two Sum
      • Isomorphic Strings
      • Minimum Index Sum of Two Lists
      • First Unique Character in a String
      • Intersection of Two Arrays II
      • Logger Rate Limiter
      • Group Anagrams
      • Group Shifted Strings
      • Find Duplicate Subtrees
      • 4Sum II
      • Top K Frequent Elements
      • Unique Word Abbreviation
      • Insert Delete GetRandom O(1)
    • Binary Tree
      • Binary Tree Preorder Traversal
      • Binary Tree Inorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Maximum Depth of Binary Tree
      • Symmetric Tree
      • Path Sum
      • Balanced Binary Tree
      • Count Univalue Subtrees
      • Construct Binary Tree from Inorder and Postorder Traversal
      • Construct Binary Tree from Preorder and Inorder Traversal
      • Populating Next Right Pointers in Each Node
      • Lowest Common Ancestor of a Binary Tree
      • Serialize and Deserialize Binary Tree
      • Median of Two Sorted Arrays
      • Invert Binary Tree
      • Find K-th Smallest Pair Distance
      • Split Array Largest Sum
    • Heap
    • Binary Search Tree
      • Validate Binary Search Tree
      • Inorder Successor in BST
      • Binary Search Tree Iterator
      • Search in a Binary Search Tree
      • Insert into a Binary Search Tree
      • Delete Node in a BST
      • Kth Largest Element in a Stream
      • Lowest Common Ancestor of a Binary Search Tree
      • Contains Duplicate III
      • Height-Balanced BST
        • Balanced Binary Tree
        • Convert Sorted Array to Binary Search Tree
    • Map
    • N-ary Tree
      • N-ary Tree Preorder Traversal
      • N-ary Tree Postorder Traversal
      • N-ary Tree Level Order Traversal
      • Maximum Depth of N-ary Tree
      • Encode N-ary Tree to Binary Tree
      • Serialize and Deserialize N-ary Tree
    • Trie
      • Implement Trie (Prefix Tree)
      • Map Sum Pairs
      • Replace Words
      • Design Search Autocomplete System
      • Maximum XOR of Two Numbers in an Array
      • Add and Search Word - Data structure design
      • Word Search II
      • Word Squares
      • Longest Common Prefix
      • Palindrome Pairs
    • Balanced Tree
      • B-Tree
      • Red-black Tree
      • AVL Tree
    • Graph
      • A* Search
      • Breadth First Search
      • Depth First Search
      • Dijkstra Algorithm
  • Sequences
    • Fibonacci Sequence
  • Dynamic Programming
    • Knapsack problem
    • Climbing Stairs
    • Best Time to Buy and Sell Stock
    • Maximum Subarray
    • House Robber
  • Interviews
    • Google Leetcode
      • Repeated String Match
      • K Empty Slots
      • Next Closest Time
      • Longest Univalue Path
      • License Key Formatting
      • Spiral Matrix
      • Plus One
      • Trapping Rain Water
      • Longest Substring with At Most K Distinct Characters
      • Add Bold Tag in String
      • Game of Life
      • Read N Characters Given Read4
      • Read N Characters Given Read4 II - Call multiple times
      • One Edit Distance
      • Valid Palindrome
      • Valid Number
      • Valid Parentheses
      • Image Smoother
      • Intersection of Two Arrays
      • Max Consecutive Ones
      • Max Consecutive Ones II
      • Shortest Palindrome
      • First Missing Positive
      • First Unique Character in a String
      • Move Zeroes
      • Remove Duplicates from Sorted Array
      • Merge k Sorted Lists
      • Insert into a Cyclic Sorted List
      • Evaluate Division
      • Inorder Successor in BST
      • Robot Room Cleaner
      • Redundant Connection II
      • Course Schedule
      • Validate Binary Search Tree
      • Closest Binary Search Tree Value
      • Word Squares
      • Strobogrammatic Number II
      • Word Search II
      • Android Unlock Patterns
      • Minimum Window Substring
      • Kth Largest Element in an Array
      • Shortest Distance from All Buildings
      • Find K-th Smallest Pair Distance
      • Find K Pairs with Smallest Sums
      • Range Module
      • Insert Interval
      • Sort Transformed Array
      • Merge Intervals
      • Longest Palindromic Substring
      • Next Greater Element I
      • Pacific Atlantic Water Flow
      • Evaluate Reverse Polish Notation
      • Decode Ways
      • Word Break
      • Sentence Screen Fitting
      • Maximum Vacation Days
      • Edit Distance
      • Minimum Path Sum
      • House Robber II
      • Moving Average from Data Stream
      • Peeking Iterator
      • Binary Search Tree Iterator
      • Zigzag Iterator
      • Design Tic-Tac-Toe
      • Range Sum Query 2D - Mutable
      • UTF-8 Validation
      • Maximum Product of Word Lengths
  • Other
    • Game of Life
Powered by GitBook
On this page

Was this helpful?

  1. Data Structures
  2. Trie

Implement Trie (Prefix Tree)

Implement a trie withinsert,search, andstartsWithmethods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

  • You may assume that all inputs are consist of lowercase lettersa-z

  • All inputs are guaranteed to be non-empty strings.

Solution

class Trie {

    static class TrieNode {
        char value;
        boolean isWord;
        Map<Character, TrieNode> children = new HashMap<>();
        TrieNode(char value) {
            this.value = value;
        }
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Queue<TrieNode> queue = new LinkedList<>();
            queue.offer(this);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    TrieNode node = queue.poll();
                    sb.append(node.value);
                    for (Map.Entry<Character, TrieNode> child : node.children.entrySet()) {
                        queue.offer(child.getValue());
                    }
                }
            }
            return sb.toString();
        }
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode(' ');    
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode current = root;
        TrieNode last = null;
        int index = 0;
        while (index < word.length()) {
            char c = word.charAt(index);
            if (current.children.containsKey(c)) {
                current = current.children.get(c);
            } else {
                last = new TrieNode(c);
                current.children.put(c, last);
                current = last;
            } 
            index++;
        }
        if (current != null) {
            current.isWord = true;
        }
        //System.out.println(root);
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode current = root;
        int index = 0;
        while (index < word.length()) {
            char c = word.charAt(index);
            if (current.children.containsKey(c)) {
                current = current.children.get(c);
            } else {
                return false;
            } 
            index++;
        }
        return current.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        int index = 0;
        while (index < prefix.length()) {
            char c = prefix.charAt(index);
            if (current.children.containsKey(c)) {
                current = current.children.get(c);
            } else {
                return false;
            } 
            index++;
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Another implementation.

class Trie {
    class TrieNode {
        public boolean isWord; 
        public Map<Character, TrieNode> childrenMap = new HashMap<>();
    }

    private TrieNode root; 

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(cur.childrenMap.get(c) == null){
                // insert a new node if the path does not exist
                cur.childrenMap.put(c, new TrieNode());
            }
            cur = cur.childrenMap.get(c); 
        }
        cur.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode cur = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.childrenMap.get(c) == null) {
                return false;
            }
            cur = cur.childrenMap.get(c);
        }
        return cur.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for(int i = 0;i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(cur.childrenMap.get(c) == null) {
                return false;
            }
            cur = cur.childrenMap.get(c);
        }
        return true;
    }
}
PreviousTrieNextMap Sum Pairs

Last updated 5 years ago

Was this helpful?