Katkat
Back

Determine string segmentability with dictionary

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine string segmentability with dictionary states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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).