LeetCode 820: Short Encoding of Words
A suffix-removal solution for finding the shortest reference string that can encode every word.
Tag
Trie
20 notes
LeetCode 720: Longest Word in Dictionary
A clear explanation of finding the longest buildable word using sorting and a hash set.
LeetCode 745: Prefix and Suffix Search
Support fast prefix and suffix queries by indexing every prefix-suffix combination with the largest word index.
LeetCode 677: Map Sum Pairs
Design a map that supports key-value insertion and prefix-sum queries using a hash map and trie.
LeetCode 648: Replace Words
A trie-based solution for replacing each derivative word with the shortest matching root.
LeetCode 642: Design Search Autocomplete System
A trie-based design for returning the top three historical sentences for a typed prefix.
LeetCode 588: Design In-Memory File System
A clear design guide for implementing an in-memory file system with directory listing, directory creation, file append, and file read operations.
LeetCode 527: Word Abbreviation
A clear explanation of generating minimal unique word abbreviations using grouping and trie prefixes.
LeetCode 472: Concatenated Words
A clear explanation of finding all words that can be formed by concatenating at least two shorter words from the same list.
LeetCode 440: K-th Smallest in Lexicographical Order
Find the k-th integer in lexicographical order without generating all numbers, using prefix counting over a conceptual trie.
LeetCode 425: Word Squares
A clear explanation of building all word squares using backtracking with prefix pruning.
LeetCode 421: Maximum XOR of Two Numbers in an Array
A clear explanation of finding the maximum XOR of two numbers using greedy bit prefixes.
LeetCode 386: Lexicographical Numbers
A clear explanation of generating numbers from 1 to n in lexicographical order using an iterative DFS-style traversal.
LeetCode 336: Palindrome Pairs
A clear explanation of Palindrome Pairs using reversed-word lookup and palindrome split checks.
LeetCode 212: Word Search II
A clear explanation of finding multiple words in a character board using a Trie and DFS backtracking.
LeetCode 211: Design Add and Search Words Data Structure
A clear explanation of designing a word dictionary with addWord and wildcard search using a Trie and DFS.
LeetCode 208: Implement Trie Prefix Tree
A clear explanation of implementing a Trie with insert, search, and startsWith operations.
LeetCode 139: Word Break
Decide whether a string can be segmented into dictionary words using dynamic programming over prefixes.
2.6 Tries and Prefix Structures
Trie variants including compressed, Patricia, ternary, XOR, suffix trees, Aho-Corasick, DAWG, HAMT, and concurrent prefix structures.
Trie Search
Search for a string key in a prefix tree by following character transitions.