Tries

A trie (prefix tree) stores words letter by letter, so words that start the same share a path — like a phone's autocomplete. Any "starts with…" question becomes a short walk down the tree.

After this topic: You can build a trie, add wildcard search, and prune a search over a grid with it.

Do these first: Trees

0 of 3 solved0%

Step 1 · Read the lesson

Tries

Store words letter by letter so any prefix question is a short walk down a tree.

Step 2 · Solve the problems in order

Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.

1.Implement Trie (Prefix Tree)Medium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

type Trie struct{}
func Constructor() Trie
func (t *Trie) Insert(word string)
func (t *Trie) Search(word string) bool
func (t *Trie) StartsWith(prefix string) bool

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Tries lesson page.

// Trie stores words letter by letter, so words that share a beginning share a path.
type node struct {
	next map[rune]*node
	end  bool // a word finishes exactly here
}

type Trie struct{ root *node }

func NewTrie() *Trie { return &Trie{root: &node{next: map[rune]*node{}}} }

func (t *Trie) Insert(word string) {
	cur := t.root
	for _, r := range word {
		child, ok := cur.next[r]
		if !ok { // 1. no edge for this letter yet: create it
			child = &node{next: map[rune]*node{}}
			cur.next[r] = child
		}
		cur = child // 2. walk down one letter
	}
	cur.end = true // 3. mark the word's last node
}

// walk follows prefix from the root and returns the node it ends on, or nil.
func (t *Trie) walk(prefix string) *node {
	cur := t.root
	for _, r := range prefix {
		cur = cur.next[r]
		if cur == nil {
			return nil // 4. the path breaks: nothing stored starts with this prefix
		}
	}
	return cur
}

// Search reports whether the exact word was inserted.
func (t *Trie) Search(word string) bool {
	n := t.walk(word)
	return n != nil && n.end
}

// StartsWith reports whether any inserted word begins with prefix.
func (t *Trie) StartsWith(prefix string) bool { return t.walk(prefix) != nil }

2.Design Add and Search WordsMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

type WordDictionary struct{}
func Constructor() WordDictionary
func (w *WordDictionary) AddWord(word string)
func (w *WordDictionary) Search(word string) bool

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Tries lesson page.

// WordDictionary: Search treats '.' as "any single letter".
type WordDictionary struct{ t *Trie }

func NewWordDictionary() *WordDictionary { return &WordDictionary{t: NewTrie()} }

func (w *WordDictionary) AddWord(word string) { w.t.Insert(word) }

func (w *WordDictionary) Search(word string) bool {
	var match func(n *node, rest []rune) bool
	match = func(n *node, rest []rune) bool {
		if len(rest) == 0 {
			return n.end
		}
		if rest[0] == '.' { // wildcard: try every child
			for _, child := range n.next {
				if match(child, rest[1:]) {
					return true
				}
			}
			return false
		}
		child := n.next[rest[0]]
		return child != nil && match(child, rest[1:])
	}
	return match(w.t.root, []rune(word))
}

3.Word Search IIHard

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func findWords(board [][]byte, words []string) []string

Tested with go test. Try it yourself first, then compare.

// FindWords searches the board for many words at once. Insert all words into a trie, then DFS from each cell
// following trie edges: a branch with no matching child is pruned immediately. Found words are removed from
// the trie so they are reported once.
type wsNode struct {
	next map[byte]*wsNode
	word string // non-empty when a word ends here
}

func FindWords(board [][]byte, words []string) []string {
	root := &wsNode{next: map[byte]*wsNode{}}
	for _, w := range words {
		n := root
		for i := 0; i < len(w); i++ {
			if n.next[w[i]] == nil {
				n.next[w[i]] = &wsNode{next: map[byte]*wsNode{}}
			}
			n = n.next[w[i]]
		}
		n.word = w
	}
	found := []string{}
	var dfs func(r, c int, n *wsNode)
	dfs = func(r, c int, n *wsNode) {
		if r < 0 || c < 0 || r >= len(board) || c >= len(board[0]) {
			return
		}
		ch := board[r][c]
		child := n.next[ch]
		if ch == '#' || child == nil {
			return // already used on this path, or no word continues this way
		}
		if child.word != "" {
			found = append(found, child.word)
			child.word = "" // report each word once
		}
		board[r][c] = '#' // mark as used
		dfs(r+1, c, child)
		dfs(r-1, c, child)
		dfs(r, c+1, child)
		dfs(r, c-1, child)
		board[r][c] = ch // restore
	}
	for r := range board {
		for c := range board[r] {
			dfs(r, c, root)
		}
	}
	return found
}