1. Implement Trie Prefix Tree
Medium · LC 208
Implement a trie supporting insert, search for a full word, and startsWith for a prefix. Each node holds a children map or 26-slot array plus an isEnd flag; insert walks the word creating missing children and marks the last node, while both queries walk without creating. The only difference between search and startsWith is whether the final node's isEnd flag must be true.
class Trie:
"""LC 208. Implement Trie (Prefix Tree).
Each node is a dict of children keyed by letter plus an is_word_end
flag; here every node is simply a Trie instance, so the structure is
self-similar with no helper class. insert walks the word creating
missing children and flags the last node; search and startsWith walk
without creating, differing only in whether the final node's
is_word_end flag must be set. All three are O(L) time for a word of
length L; space is O(total letters inserted).
"""
def __init__(self):
self.children_by_letter: dict[str, "Trie"] = {}
self.is_word_end = False
def insert(self, word: str) -> None:
node = self
for letter in word:
if letter not in node.children_by_letter:
node.children_by_letter[letter] = Trie()
node = node.children_by_letter[letter]
node.is_word_end = True # flag distinguishes a word from a mere prefix
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.is_word_end
def startsWith(self, prefix: str) -> bool:
return self._walk(prefix) is not None
def _walk(self, letters: str) -> "Trie | None":
"""Follow letters down the trie; None the moment a hop is missing."""
node = self
for letter in letters:
node = node.children_by_letter.get(letter)
if node is None:
return None
return node
// LC 208. insert walks the word creating missing children and marks the last
// node; search and startsWith share one read-only walk, differing only in
// whether the final node's isWordEnd flag must be true. All three are
// O(word length).
class Trie {
public:
void insert(string word) {
TrieNode* node = &root;
for (char c : word) {
TrieNode*& child = node->children[c - 'a'];
if (!child) child = new TrieNode();
node = child;
}
node->isWordEnd = true;
}
bool search(string word) {
TrieNode* node = walk(word);
return node && node->isWordEnd;
}
bool startsWith(string prefix) { return walk(prefix) != nullptr; }
private:
TrieNode root;
TrieNode* walk(const string& s) { // node for s, or null if the path breaks
TrieNode* node = &root;
for (char c : s) {
node = node->children[c - 'a'];
if (!node) return nullptr;
}
return node;
}
};
/// LC 208. Insert walks the word creating missing children; both queries
/// walk without creating, and the only difference between search and
/// starts_with is whether the final node's is_end flag must be true.
pub struct Trie {
nodes: Vec<TrieNode>,
}
impl TrieNode {
fn new() -> Self {
TrieNode { children: [0; 26], is_end: false }
}
}
/** LC 208. insert creates missing children and marks the last node; search vs startsWith differ only in checking isWordEnd. */
export class Trie {
private root = new TrieNode();
insert(word: string): void {
let node = this.root;
for (const ch of word) {
let child = node.children.get(ch);
if (!child) {
child = new TrieNode();
node.children.set(ch, child);
}
node = child;
}
node.isWordEnd = true;
}
search(word: string): boolean {
const node = this.walk(word);
return node !== null && node.isWordEnd;
}
startsWith(prefix: string): boolean {
return this.walk(prefix) !== null;
}
/** Follows the string without creating nodes; null means the path falls off the trie. */
private walk(s: string): TrieNode | null {
let node = this.root;
for (const ch of s) {
const child = node.children.get(ch);
if (!child) return null;
node = child;
}
return node;
}
}
// Trie is LC 208: each node is a 26-slot child array plus an isWordEnd flag,
// and every node is simply a Trie, so the structure is self-similar. insert
// creates missing children and flags the last node; search and startsWith
// share one read-only walk. All three are O(word length).
type Trie struct {
children [26]*Trie
isWordEnd bool
}
func newTrie() *Trie {
return &Trie{}
}
func (t *Trie) insert(word string) {
node := t
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil {
node.children[c] = &Trie{}
}
node = node.children[c]
}
node.isWordEnd = true // flag distinguishes a word from a mere prefix
}
func (t *Trie) search(word string) bool {
node := t.walk(word)
return node != nil && node.isWordEnd
}
func (t *Trie) startsWith(prefix string) bool {
return t.walk(prefix) != nil
}
// walk follows letters down the trie; nil the moment a hop is missing.
func (t *Trie) walk(letters string) *Trie {
node := t
for i := 0; i < len(letters); i++ {
node = node.children[letters[i]-'a']
if node == nil {
return nil
}
}
return node
}
// LC 208. Each node is a children-by-letter dictionary plus an isWordEnd
// flag; insert creates missing children and flags the last node, while
// search and startsWith share one read-only walk, differing only in whether
// that final flag must be set.
class Trie {
class TrieNode {
var children: [Character: TrieNode] = [:]
var isWordEnd = false
}
let root = TrieNode()
func insert(_ word: String) {
var node = root
for letter in word {
if node.children[letter] == nil { node.children[letter] = TrieNode() }
node = node.children[letter]!
}
node.isWordEnd = true // flag distinguishes a word from a mere prefix
}
func search(_ word: String) -> Bool {
guard let node = walk(word) else { return false }
return node.isWordEnd
}
func startsWith(_ prefix: String) -> Bool { return walk(prefix) != nil }
func walk(_ letters: String) -> TrieNode? { // nil the moment a hop is missing
var node = root
for letter in letters {
guard let child = node.children[letter] else { return nil }
node = child
}
return node
}
}
2. Design Add And Search Words Data Structure
Medium · LC 211
Design a structure with addWord and a search where a dot character matches any single letter. Store the words in a trie; search runs a DFS that follows the matching child for a literal letter but branches into all children on a dot. Success requires consuming the whole query and landing on a node with isEnd set; the wildcard is what forces recursion over plain iteration.
class WordDictionary:
"""LC 211. Design Add and Search Words Data Structure.
A trie again (each node a WordDictionary instance with a children
dict and an is_word_end flag), but search must handle '.' matching
any single letter. A literal letter follows one child; a dot has no
single child to follow, so the DFS branches into ALL children and
succeeds if any branch consumes the rest of the pattern ending on a
word-end node. The wildcard is what forces recursion over plain
iteration. addWord is O(L); search is O(L) for literal queries and
up to O(26^d * L) with d dots. Space is O(total letters added).
"""
def __init__(self):
self.children_by_letter: dict[str, "WordDictionary"] = {}
self.is_word_end = False
def addWord(self, word: str) -> None:
node = self
for letter in word:
if letter not in node.children_by_letter:
node.children_by_letter[letter] = WordDictionary()
node = node.children_by_letter[letter]
node.is_word_end = True
def search(self, word: str) -> bool:
def matches_from(node: "WordDictionary", i: int) -> bool:
if i == len(word):
return node.is_word_end # whole pattern consumed; must be a word
letter = word[i]
if letter == ".": # wildcard: try every child, any success wins
return any(
matches_from(child, i + 1)
for child in node.children_by_letter.values()
)
child = node.children_by_letter.get(letter)
return child is not None and matches_from(child, i + 1)
return matches_from(self, 0)
// LC 211. Words live in a trie; search is a DFS that follows the single
// matching child for a literal letter but branches into ALL children on '.'.
// A match must consume the whole query AND land on an isWordEnd node -- the
// wildcard is what forces recursion over plain iteration.
class WordDictionary {
public:
void addWord(string word) {
TrieNode* node = &root;
for (char c : word) {
TrieNode*& child = node->children[c - 'a'];
if (!child) child = new TrieNode();
node = child;
}
node->isWordEnd = true;
}
bool search(string word) {
auto dfs = [&](auto&& self, TrieNode* node, int i) -> bool {
if (!node) return false;
if (i == static_cast<int>(word.size())) return node->isWordEnd;
if (word[i] != '.') return self(self, node->children[word[i] - 'a'], i + 1);
for (TrieNode* child : node->children)
if (child && self(self, child, i + 1)) return true;
return false;
};
return dfs(dfs, &root, 0);
}
private:
TrieNode root;
};
/// LC 211. Same arena trie as LC 208; search runs a DFS that follows the one
/// matching child for a literal letter but branches into ALL children on a
/// '.' -- the wildcard is what forces recursion over plain iteration.
pub struct WordDictionary {
nodes: Vec<TrieNode>,
}
impl WordDictionary {
pub fn new() -> Self {
WordDictionary { nodes: vec![TrieNode::new()] }
}
pub fn add_word(&mut self, word: String) {
let mut node = 0;
for b in word.bytes() {
let slot = (b - b'a') as usize;
if self.nodes[node].children[slot] == 0 {
self.nodes.push(TrieNode::new());
let fresh = self.nodes.len() - 1;
self.nodes[node].children[slot] = fresh;
}
node = self.nodes[node].children[slot];
}
self.nodes[node].is_end = true;
}
pub fn search(&self, word: String) -> bool {
self.dfs(word.as_bytes(), 0)
}
fn dfs(&self, word: &[u8], node: usize) -> bool {
// Success = whole query consumed AND landing on an end-of-word node.
let Some((&b, rest)) = word.split_first() else {
return self.nodes[node].is_end;
};
if b == b'.' {
self.nodes[node]
.children
.iter()
.any(|&child| child != 0 && self.dfs(rest, child))
} else {
let child = self.nodes[node].children[(b - b'a') as usize];
child != 0 && self.dfs(rest, child)
}
}
}
/** LC 211. Trie + DFS search: a literal letter follows one child, a '.' branches into ALL children. */
export class WordDictionary {
private root = new TrieNode();
addWord(word: string): void {
let node = this.root;
for (const ch of word) {
let child = node.children.get(ch);
if (!child) {
child = new TrieNode();
node.children.set(ch, child);
}
node = child;
}
node.isWordEnd = true;
}
search(word: string): boolean {
function dfs(node: TrieNode, i: number): boolean {
if (i === word.length) return node.isWordEnd; // must consume the whole query
const ch = word[i];
if (ch === ".") {
// the wildcard is what forces recursion over plain iteration
for (const child of node.children.values()) {
if (dfs(child, i + 1)) return true;
}
return false;
}
const child = node.children.get(ch);
return child !== undefined && dfs(child, i + 1);
}
return dfs(this.root, 0);
}
}
// WordDictionary is LC 211: a trie again, but search must handle '.' matching
// any single letter. A literal letter follows one child; a dot fans the DFS
// into ALL children -- the wildcard is what forces recursion over iteration.
type WordDictionary struct {
children [26]*WordDictionary
isWordEnd bool
}
func newWordDictionary() *WordDictionary {
return &WordDictionary{}
}
func (d *WordDictionary) addWord(word string) {
node := d
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil {
node.children[c] = &WordDictionary{}
}
node = node.children[c]
}
node.isWordEnd = true
}
func (d *WordDictionary) search(word string) bool {
var matchesFrom func(node *WordDictionary, i int) bool
matchesFrom = func(node *WordDictionary, i int) bool {
if node == nil {
return false
}
if i == len(word) {
return node.isWordEnd // whole pattern consumed; must be a word
}
if word[i] == '.' { // wildcard: try every child, any success wins
for _, child := range node.children {
if child != nil && matchesFrom(child, i+1) {
return true
}
}
return false
}
return matchesFrom(node.children[word[i]-'a'], i+1)
}
return matchesFrom(d, 0)
}
// LC 211. Words live in a trie; search is a DFS that follows the single
// matching child for a literal letter but fans into ALL children on '.'.
// A match must consume the whole query AND land on a word-end node -- the
// wildcard is what forces recursion over plain iteration.
class WordDictionary {
class TrieNode {
var children: [Character: TrieNode] = [:]
var isWordEnd = false
}
let root = TrieNode()
func addWord(_ word: String) {
var node = root
for letter in word {
if node.children[letter] == nil { node.children[letter] = TrieNode() }
node = node.children[letter]!
}
node.isWordEnd = true
}
func search(_ word: String) -> Bool {
let pattern = Array(word)
func matchesFrom(_ node: TrieNode, _ i: Int) -> Bool {
if i == pattern.count { return node.isWordEnd } // whole pattern consumed
if pattern[i] == "." { // wildcard: try every child, any success wins
return node.children.values.contains { matchesFrom($0, i + 1) }
}
guard let child = node.children[pattern[i]] else { return false }
return matchesFrom(child, i + 1)
}
return matchesFrom(root, 0)
}
}
3. Extra Characters in a String
Medium · LC 2707
Given a string s and a dictionary, break s into non-overlapping dictionary words and return the minimum number of leftover characters belonging to no word. Define dp[i] as the minimum extras from index i onward: either waste s[i] for dp[i+1] plus one, or jump past any dictionary word starting at i. Walking a trie from position i discovers all matching words in one descent, replacing repeated substring lookups.
def min_extra_char(s: str, dictionary: list[str]) -> int:
"""LC 2707. Extra Characters in a String.
Suffix dp: extras[i] is the minimum number of leftover letters in
s[i:]. From each i either waste s[i] (extras[i+1] + 1) or jump past
any dictionary word starting at i (extras at the index after the
word). A trie of the dictionary finds all those jumps in one
descent: walk children letter by letter from position i, and every
word-end node passed is a jump. The trie prunes hard -- the moment
s[j] has no child, NO dictionary word starting at i can extend
through j, so the inner walk stops instead of testing every longer
substring against a set. O(n^2 + total dictionary letters) time,
O(n + total dictionary letters) space.
"""
WORD_END = "$" # sentinel key: cannot collide with single letters
trie_root: dict = {} # each node is just a children-by-letter dict
for word in dictionary:
node = trie_root
for letter in word:
node = node.setdefault(letter, {})
node[WORD_END] = True
n = len(s)
extras = [0] * (n + 1) # extras[n] = 0: empty suffix has nothing left over
for i in range(n - 1, -1, -1):
extras[i] = extras[i + 1] + 1 # default: s[i] is an extra character
node = trie_root
for j in range(i, n):
node = node.get(s[j])
if node is None: # trie prunes: no word starting at i continues here
break
if WORD_END in node: # s[i:j+1] is a dictionary word -> jump over it
extras[i] = min(extras[i], extras[j + 1])
return extras[0]
// LC 2707. dp[i] = minimum extra characters in the suffix s[i:]. Either waste
// s[i] (dp[i+1] + 1) or jump past any dictionary word starting at i. One trie
// descent from position i discovers every matching word in O(longest word)
// instead of testing each substring separately. O(n * longest word + dict).
int minExtraChar(string s, vector<string> dictionary) {
TrieNode root;
for (const string& word : dictionary) {
TrieNode* node = &root;
for (char c : word) {
TrieNode*& child = node->children[c - 'a'];
if (!child) child = new TrieNode();
node = child;
}
node->isWordEnd = true;
}
int n = static_cast<int>(s.size());
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
dp[i] = dp[i + 1] + 1; // waste s[i]
TrieNode* node = &root;
for (int j = i; j < n; ++j) { // every dictionary word starting at i
node = node->children[s[j] - 'a'];
if (!node) break;
if (node->isWordEnd) dp[i] = min(dp[i], dp[j + 1]);
}
}
return dp[0];
}
/// LC 2707. dp[i] = min extras over the suffix s[i..]: either waste s[i]
/// (dp[i+1] + 1) or jump past a dictionary word starting at i. Walking the
/// trie from position i discovers ALL matching words in one descent, instead
/// of a HashSet lookup per (i, j) substring.
pub fn min_extra_char(s: String, dictionary: Vec<String>) -> i32 {
let mut trie = Trie::new();
for word in dictionary {
trie.insert(word);
}
let bytes = s.as_bytes();
let n = bytes.len();
let mut dp = vec![0i32; n + 1];
for i in (0..n).rev() {
dp[i] = dp[i + 1] + 1; // give up on s[i]
let mut node = 0;
for j in i..n {
node = trie.nodes[node].children[(bytes[j] - b'a') as usize];
if node == 0 {
break; // no dictionary word continues this prefix
}
if trie.nodes[node].is_end {
dp[i] = dp[i].min(dp[j + 1]);
}
}
}
dp[0]
}
/** LC 2707. dp[i] = min extras in s[i:]; one trie descent from i finds every dictionary word starting there. */
export function minExtraChar(s: string, dictionary: string[]): number {
const root = new TrieNode();
for (const word of dictionary) {
let node = root;
for (const ch of word) {
let child = node.children.get(ch);
if (!child) {
child = new TrieNode();
node.children.set(ch, child);
}
node = child;
}
node.isWordEnd = true;
}
const n = s.length;
const dp = new Array<number>(n + 1).fill(0); // dp[n] = 0: empty suffix has no extras
for (let i = n - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + 1; // waste s[i] as an extra character
let node: TrieNode | undefined = root;
for (let j = i; j < n; j++) {
node = node.children.get(s[j]);
if (!node) break; // no dictionary word continues through s[i..j]
if (node.isWordEnd) dp[i] = Math.min(dp[i], dp[j + 1]); // jump past the word s[i..j]
}
}
return dp[0];
}
// LC 2707. Suffix dp: dp[i] is the minimum leftover letters in s[i:]; either
// waste s[i] or jump past any dictionary word starting at i, all found by one
// trie descent that stops the moment no word continues.
func minExtraChar(s string, dictionary []string) int {
type trieNode struct {
children [26]*trieNode
isWordEnd bool
}
root := &trieNode{}
for _, word := range dictionary {
node := root
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil {
node.children[c] = &trieNode{}
}
node = node.children[c]
}
node.isWordEnd = true
}
n := len(s)
dp := make([]int, n+1) // dp[n] = 0: the empty suffix has nothing left over
for i := n - 1; i >= 0; i-- {
dp[i] = dp[i+1] + 1 // default: s[i] is an extra character
node := root
for j := i; j < n; j++ { // every dictionary word starting at i
node = node.children[s[j]-'a']
if node == nil {
break // trie prunes: no word starting at i continues here
}
if node.isWordEnd && dp[j+1] < dp[i] {
dp[i] = dp[j+1] // s[i:j+1] is a word -> jump over it
}
}
}
return dp[0]
}
// LC 2707. Suffix dp: extras[i] is the minimum leftover letters in s[i...];
// either waste s[i] or jump past any dictionary word starting at i, and one
// trie descent from i discovers every such jump, pruning the moment no word
// continues.
func minExtraChar(_ s: String, _ dictionary: [String]) -> Int {
class TrieNode {
var children: [Character: TrieNode] = [:]
var isWordEnd = false
}
let root = TrieNode()
for word in dictionary {
var node = root
for letter in word {
if node.children[letter] == nil { node.children[letter] = TrieNode() }
node = node.children[letter]!
}
node.isWordEnd = true
}
let letters = Array(s)
let n = letters.count
var extras = Array(repeating: 0, count: n + 1) // extras[n] = 0: empty suffix
for i in stride(from: n - 1, through: 0, by: -1) {
extras[i] = extras[i + 1] + 1 // default: s[i] is an extra character
var node = root
for j in i..<n {
guard let child = node.children[letters[j]] else { break } // trie prunes
node = child
if node.isWordEnd { extras[i] = min(extras[i], extras[j + 1]) } // jump over the word
}
}
return extras[0]
}
4. Word Search II
Hard · LC 212
Given a grid of letters and a list of words, return every word that can be traced through adjacent cells without reusing a cell. Build a trie of all the words, then one DFS per starting cell walks the board and the trie in lockstep, abandoning any path lacking a trie child. Store each word at its end node to collect matches cleanly, and prune exhausted trie leaves so later searches stay fast.
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
"""LC 212. Word Search II.
Build one trie of all the words, storing each full word at its end
node, then run a single grid DFS per starting cell that walks the
board and the trie in lockstep -- any path lacking a trie child is
abandoned immediately, so one traversal hunts every word at once.
Two prunes keep repeat searches fast: pop the stored word from its
node when found (collects each word once, no duplicate hits), and
delete a child from its parent once it has no children left, so
later DFS calls never re-walk exhausted trie branches. O(W * L) to
build the trie, O(rows * cols * 4 * 3^(L-1)) DFS worst case.
"""
WORD_AT_END = "$" # sentinel key holding the full word at its end node
trie_root: dict = {}
for word in words:
node = trie_root
for letter in word:
node = node.setdefault(letter, {})
node[WORD_AT_END] = word
rows, cols = len(board), len(board[0])
found: list[str] = []
def explore(row: int, col: int, parent: dict) -> None:
letter = board[row][col]
child = parent.get(letter)
if child is None: # no word continues with this letter -- abandon path
return
word = child.pop(WORD_AT_END, None)
if word is not None: # popping claims the word: it can never match twice
found.append(word)
board[row][col] = "#" # mark visited in place; restored below
for next_row, next_col in (
(row - 1, col),
(row + 1, col),
(row, col - 1),
(row, col + 1),
):
if 0 <= next_row < rows and 0 <= next_col < cols and board[next_row][next_col] != "#":
explore(next_row, next_col, child)
board[row][col] = letter
if not child: # prune: every word through this node is found, delete it
del parent[letter]
for row in range(rows):
for col in range(cols):
explore(row, col, trie_root)
return found
// LC 212. Build one trie of all the words, then a DFS from each cell walks
// the board and the trie in lockstep, abandoning any path with no trie child.
// Each end node stores its word: emit it once and clear it (dedupe), and
// prune exhausted leaf nodes from their parent so later searches skip dead
// branches. Visited cells are marked in place with '#'.
vector<string> findWords(vector<vector<char>> board, vector<string> words) {
TrieNode root;
for (const string& word : words) {
TrieNode* node = &root;
for (char c : word) {
TrieNode*& child = node->children[c - 'a'];
if (!child) child = new TrieNode();
node = child;
}
node->word = word; // the end node remembers its word
}
int rows = static_cast<int>(board.size());
int cols = static_cast<int>(board[0].size());
vector<string> ans;
auto dfs = [&](auto&& self, int row, int col, TrieNode* node) -> void {
char letter = board[row][col];
if (letter == '#') return; // cell already on the current path
TrieNode* next = node->children[letter - 'a'];
if (!next) return; // no word continues this way
if (!next->word.empty()) {
ans.push_back(next->word);
next->word.clear(); // report each word once
}
board[row][col] = '#';
if (row > 0) self(self, row - 1, col, next);
if (row + 1 < rows) self(self, row + 1, col, next);
if (col > 0) self(self, row, col - 1, next);
if (col + 1 < cols) self(self, row, col + 1, next);
board[row][col] = letter;
bool hasChild = false; // prune: drop nodes with nothing left to find
for (TrieNode* child : next->children)
if (child) hasChild = true;
if (!hasChild && next->word.empty()) {
delete next;
node->children[letter - 'a'] = nullptr;
}
};
for (int row = 0; row < rows; ++row)
for (int col = 0; col < cols; ++col) dfs(dfs, row, col, &root);
return ans;
}
/// LC 212. One trie of all the words, then a DFS per starting cell walks the
/// board and the trie in lockstep, abandoning any path lacking a trie child.
/// After backtracking, exhausted leaves (no word left, no children) are
/// unlinked from their parent so later cells never re-walk dead branches.
pub fn find_words(board: Vec<Vec<char>>, words: Vec<String>) -> Vec<String> {
fn dfs(
board: &mut [Vec<char>],
r: usize,
c: usize,
parent: usize,
nodes: &mut Vec<FoundNode>,
out: &mut Vec<String>,
) {
let ch = board[r][c];
if ch == '#' {
return; // cell already used on this path
}
let slot = (ch as u8 - b'a') as usize;
let node = nodes[parent].children[slot];
if node == 0 {
return; // no word continues through this letter
}
if let Some(word) = nodes[node].word.take() {
out.push(word); // found; take() prevents duplicates
}
board[r][c] = '#';
if r > 0 {
dfs(board, r - 1, c, node, nodes, out);
}
if r + 1 < board.len() {
dfs(board, r + 1, c, node, nodes, out);
}
if c > 0 {
dfs(board, r, c - 1, node, nodes, out);
}
if c + 1 < board[r].len() {
dfs(board, r, c + 1, node, nodes, out);
}
board[r][c] = ch;
// Found-word pruning: unlink the child once it can match nothing.
if nodes[node].word.is_none() && nodes[node].children.iter().all(|&x| x == 0) {
nodes[parent].children[slot] = 0;
}
}
let mut nodes = vec![FoundNode { children: [0; 26], word: None }];
for word in words {
let mut node = 0;
for b in word.bytes() {
let slot = (b - b'a') as usize;
if nodes[node].children[slot] == 0 {
nodes.push(FoundNode { children: [0; 26], word: None });
let fresh = nodes.len() - 1;
nodes[node].children[slot] = fresh;
}
node = nodes[node].children[slot];
}
nodes[node].word = Some(word);
}
let mut board = board;
let mut out = Vec::new();
for r in 0..board.len() {
for c in 0..board[r].len() {
dfs(&mut board, r, c, 0, &mut nodes, &mut out);
}
}
out
}
/** LC 212. Trie of words + grid DFS in lockstep; prune found words and exhausted leaves to keep later searches fast. */
export function findWords(board: string[][], words: string[]): string[] {
const root = new TrieNode();
for (const word of words) {
let node = root;
for (const ch of word) {
let child = node.children.get(ch);
if (!child) {
child = new TrieNode();
node.children.set(ch, child);
}
node = child;
}
node.word = word; // store the word at its end node to collect matches cleanly
}
const rows = board.length;
const cols = board[0].length;
const found: string[] = [];
function dfs(row: number, col: number, parent: TrieNode): void {
const ch = board[row][col];
const node = parent.children.get(ch);
if (!node) return; // the trie has no path here, abandon the branch
if (node.word !== null) {
found.push(node.word);
node.word = null; // pruning: clear the word so duplicate paths cannot report it twice
}
board[row][col] = "#"; // mark visited; cells cannot be reused within one path
if (row > 0) dfs(row - 1, col, node);
if (row < rows - 1) dfs(row + 1, col, node);
if (col > 0) dfs(row, col - 1, node);
if (col < cols - 1) dfs(row, col + 1, node);
board[row][col] = ch;
// pruning: a leaf with its word already harvested is dead weight, so unlink it;
// this shrinks the trie as words are found and later DFS calls fail fast
if (node.children.size === 0 && node.word === null) {
parent.children.delete(ch);
}
}
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
dfs(row, col, root);
}
}
return found;
}
// LC 212. Build one trie of all the words, then a DFS from each cell walks
// the board and the trie in lockstep, abandoning any path with no trie child;
// found words are cleared from their node and exhausted branches pruned.
func findWords(board [][]byte, words []string) []string {
type trieNode struct {
children [26]*trieNode
word string // non-empty marks an unfound word's end
}
root := &trieNode{}
for _, word := range words {
node := root
for i := 0; i < len(word); i++ {
c := word[i] - 'a'
if node.children[c] == nil {
node.children[c] = &trieNode{}
}
node = node.children[c]
}
node.word = word // the end node remembers its word
}
rows, cols := len(board), len(board[0])
found := []string{}
var explore func(row, col int, node *trieNode)
explore = func(row, col int, node *trieNode) {
letter := board[row][col]
if letter == '#' {
return // cell already on the current path
}
next := node.children[letter-'a']
if next == nil {
return // no word continues this way
}
if next.word != "" {
found = append(found, next.word)
next.word = "" // report each word once
}
board[row][col] = '#' // mark visited in place; restored below
if row > 0 {
explore(row-1, col, next)
}
if row+1 < rows {
explore(row+1, col, next)
}
if col > 0 {
explore(row, col-1, next)
}
if col+1 < cols {
explore(row, col+1, next)
}
board[row][col] = letter
hasChild := false // prune: drop nodes with nothing left to find
for _, child := range next.children {
if child != nil {
hasChild = true
}
}
if !hasChild && next.word == "" {
node.children[letter-'a'] = nil
}
}
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
explore(row, col, root)
}
}
return found
}
// LC 212. Build one trie of all the words, then a DFS from each cell walks
// the board and the trie in lockstep, abandoning any path with no trie child.
// Each end node stores its word: emit it once and clear it (dedupe), and
// prune exhausted nodes from their parent so later searches skip dead
// branches. Visited cells are marked in place with '#'.
func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
class TrieNode {
var children: [Character: TrieNode] = [:]
var word: String? // non-nil marks an unfound word's end
}
let root = TrieNode()
for word in words {
var node = root
for letter in word {
if node.children[letter] == nil { node.children[letter] = TrieNode() }
node = node.children[letter]!
}
node.word = word // the end node remembers its word
}
var grid = board
let rows = grid.count
let cols = grid[0].count
var found: [String] = []
func explore(_ row: Int, _ col: Int, _ parent: TrieNode) {
let letter = grid[row][col]
guard let child = parent.children[letter] else { return } // no word continues this way
if let word = child.word {
found.append(word)
child.word = nil // claiming the word means it can never match twice
}
grid[row][col] = "#" // mark visited in place; restored below
for (nextRow, nextCol) in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)] {
if nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols
&& grid[nextRow][nextCol] != "#" {
explore(nextRow, nextCol, child)
}
}
grid[row][col] = letter
if child.children.isEmpty && child.word == nil {
parent.children[letter] = nil // prune: every word through this node is found
}
}
for row in 0..<rows {
for col in 0..<cols {
explore(row, col, root)
}
}
return found
}