Word Ladder Variants with Trie Optimization

Fullstack / intern coding prompt around Word Ladder-style string transformations. One version asks for all shortest sequences; another uses fuzzy string matching with a prefix-tree optimization. Requirements Given beginWord, endWord, and wordList, transform from the start word to the end word through valid dictionary words. Adjacent words in a transformation sequence differ by exactly one letter in the standard version. Return all shortest transformation sequences when that version is asked. Variant: support fuzzy string matching / tolerance, then optimize with a prefix tree. Be ready to write detailed comments and test cases. Examples beginWord = "hit" endWord = "cog" wordList = ["cot", "hot", "dot", "dog", "lot", "log"] One reported expected sequence was written as: [cog -> cot -> hot -> hit] Notes The all-shortest-sequences version is the LeetCode 126 family: BFS by levels to build parent links, then backtrack all shortest paths. Do not mark a word globally visited until the current BFS level finishes; otherwise, you can lose alternate parents that produce other shortest paths. The fuzzy-matching variant is thinner. Clarify whether tolerance means edit distance, one mismatch, prefix wildcard, or another predicate before choosing trie vs. BFS preprocessing. For trie optimization, the likely goal is reducing candidate generation for string matches rather than scanning the full dictionary for every frontier word. Preparation Implement Word Ladder II with wildcard buckets or per-position character substitution, storing child -> parents for same-level shortest paths. Test the canonical two-path case, no-end-word case, duplicate words, and a case where two parents reach the same child in the same BFS layer. For the fuzzy follow-up, sketch candidate generation for Hamming distance 1, edit distance 1, and prefix trie lookup so you can ask for the intended tolerance precisely.