dsa1 min read
Stream of Characters — Reverse Suffix Trie
Query if any word ends at the current stream position. Insert reversed words into trie; maintain suffix deque to match from current position backwards.
Read →
All Posts
1276 articles
dsa1 min read
Prefix and Suffix Search — Combined Key Trie
Find word with given prefix AND suffix. Insert 'suffix#word' for each suffix of each word into trie; query combines prefix+suffix search.
Read →
dsa1 min read
Sum of Prefix Scores of Strings — Trie Count
For each word, sum up how many other words share each of its prefixes. Trie with prefix count at each node; query each word's prefix sum.
Read →
dsa1 min read
Concatenated Words — Trie + Word Break
Find all words that can be formed by concatenating two or more words from the same list. Build trie, then run word break DP on each word.
Read →
dsa1 min read
Short Encoding of Words — Trie Suffix Dedup
Encode word list as shortest string where each word is a suffix. Words that are suffixes of others need not be separately encoded. Use trie of reversed words.
Read →
Page 114 of 256