LeetCode #745: Prefix and Suffix Search, One Trie of Suffix Hash Word

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: design WordFilter, where f(pref, suff) returns the largest index of a word that starts with pref and ends with suff. Brute force: on each query, check every word for the prefix and the suffix, which is O(N·L) per query. The key insight: for each word, insert suffix + "#" + word into a single trie, once for every suffix. A query then becomes one prefix walk of suff + "#" + pref. Every trie node stores the latest index that passes through it, so later words overwrite earlier ones. Dry run: for the word apple, the key e#apple matches f(a, e), which returns 0. Complexity: O(N·L²) to build the trie, O(L) per query, and O(N·L²) space. Problem: https://leetcode.com/problems/prefix-... Related: Implement Trie (208), Design Add and Search Words Data Structure (211), Search Suggestions System (1268) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode745 #prefixandsuffixsearch #trie #design #string #hashtable #hard #coding #codinginterview #dsa #python #google #faang #brutetobest