Tries and strings

A trie stores words so that shared prefixes are stored once. Each edge is one character, and a marker says where a complete word ends. After following a prefix, the current node stands for exactly the stored words that start with it.

Looking up a word of m characters takes O(m) time when finding a child is O(1). Space depends on all the stored prefixes and how you store children. A fixed array of 26 children is fast but uses more space. A hash map handles any characters, at some extra cost.

A search with wildcards has to try every child at a wildcard, so it can visit many nodes. It isn't O(m) in general. Combining a trie with backtracking on a grid lets many words share their prefix checks. You still have to undo the grid's "visited" marks between branches.

String matching algorithms reuse what already matched. In KMP, the prefix function records, for each prefix, the longest part that's both a proper prefix and a suffix. After a mismatch, it tells you how much of the match you can keep without rechecking the text. Trace how it falls back before you memorize the code.

Rolling hashes let you compare substrings quickly, but equal hashes don't prove equal strings. Either rule out collisions, or check each match directly. An explanation of correctness has to account for collisions.

Palindrome problems often get simpler if you think from the center. Expanding around each character and each gap between characters handles odd and even lengths in O(n²) time with O(1) extra space. Other limits may call for DP or a specialized linear algorithm. Check whether the task is to find, count, or split into palindromes.

Practice: LC 208 Implement Trie, LC 211 Design Add and Search Words, LC 212 Word Search II, LC 28 Find the Index of the First Occurrence in a String, LC 5 Longest Palindromic Substring, LC 131 Palindrome Partitioning.

Check your understanding: What is one character here: a byte, a Unicode code point, or what a reader sees as one letter? Is a prefix also a complete word? What can you keep after a mismatch? Does a hash match need checking?