NUHMAN.com

Problem Statement

Implement a trie (prefix tree) with three methods:

1. Insert(word): Inserts a word into the trie.
2. Search(word): Returns true if the word is in the trie.
3. StartsWith(prefix): Returns true if there is any word in the trie that starts with the given prefix.

Example:

go

trie := Constructor()
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

Constraints:

• All inputs are lowercase letters a-z.
• All inputs are non-empty strings.
• The total number of operations won't exceed 3 * 10^4.

Approach

A Trie (also known as a prefix tree) is a tree-like data structure that stores strings in a way that facilitates fast lookup for full words and prefixes.

Trie Node Structure:

Each node contains:

• A fixed array of 26 children (for each lowercase English letter).
• A boolean flag isEnd to mark the end of a valid word.

Go Implementation

go

package main

import "fmt"

// Define the structure for TrieNode
type TrieNode struct {
    children [26]*TrieNode
    isEnd    bool
}

// Define the Trie
type Trie struct {
    root *TrieNode
}

// Constructor to initialize the Trie
func Constructor() Trie {
    return Trie{root: &TrieNode{}}
}

// Insert a word into the Trie
func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        index := ch - 'a'
        if node.children[index] == nil {
            node.children[index] = &TrieNode{}
        }
        node = node.children[index]
    }
    node.isEnd = true
}

// Search for a full word in the Trie
func (t *Trie) Search(word string) bool {
    node := t.findNode(word)
    return node != nil && node.isEnd
}

// Check if a prefix exists in the Trie
func (t *Trie) StartsWith(prefix string) bool {
    return t.findNode(prefix) != nil
}

// Helper method to find the node corresponding to a prefix or word
func (t *Trie) findNode(s string) *TrieNode {
    node := t.root
    for _, ch := range s {
        index := ch - 'a'
        if node.children[index] == nil {
            return nil
        }
        node = node.children[index]
    }
    return node
}

// Test the Trie
func main() {
    trie := Constructor()
    trie.Insert("apple")
    fmt.Println(trie.Search("apple"))   // true
    fmt.Println(trie.Search("app"))     // false
    fmt.Println(trie.StartsWith("app")) // true
    trie.Insert("app")
    fmt.Println(trie.Search("app"))     // true
}

Explanation of the Code:

Insert(word string)

• Start from the root.
• For each character, go to the corresponding child.
• If it doesn't exist, create a new TrieNode.
• After the last character, set isEnd = true.

Search(word string)

• Use a helper findNode to traverse the trie.
• If the traversal finishes and isEnd is true, return true.

StartsWith(prefix string)

• Use the same findNode helper.
• If the traversal finishes (regardless of isEnd), return true.

findNode(s string)

• Traverses the trie according to the given string.
• Returns the last node if the path exists, otherwise returns nil.

Time Complexity

• Insert: O(L), where L is the length of the word.
• Search: O(L)
• StartsWith: O(L)

Space Complexity

• O(N * L), where N is the number of inserted words and L is the average word length.

Conclusion

LeetCode 208 is a classic data structure design problem that tests your ability to implement a Trie efficiently. Tries are extremely useful for prefix-based searching and autocomplete systems.