Determine string segmentability with dictionary
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a string s and a dictionary of words, determine whether s can be segmented into a sequence of dictionary words. Provide a dynamic-programming solution and then propose an alternative that uses a Trie to speed up prefix checks and early termination on long inputs. Discuss complexity, memory trade-offs, and how to return one valid segmentation (or all possible segmentations).
Quick Answer: This question evaluates understanding of dynamic programming, prefix-oriented data structures such as Tries, algorithmic complexity analysis, memory trade-offs, and techniques for producing one or multiple valid segmentations of a string.
