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 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 list of words `word_dict`, return `true` if `s` can be segmented into a space-separated sequence of one or more words from `word_dict`. The same dictionary word may be reused any number of times. An empty string is considered segmentable (it is the empty concatenation).
Example 1: s = "leetcode", word_dict = ["leet", "code"] -> true ("leet code").
Example 2: s = "applepenapple", word_dict = ["apple", "pen"] -> true ("apple pen apple"; "apple" is reused).
Example 3: s = "catsandog", word_dict = ["cats", "dog", "sand", "and", "cat"] -> false.
The classic O(n^2) approach is bottom-up dynamic programming: dp[i] is true iff the prefix s[:i] can be segmented; dp[i] becomes true when some split point j has dp[j] true and the substring s[j:i] is in the dictionary. An alternative builds a Trie over the dictionary so prefix checks share work and the inner scan can terminate early once no dictionary prefix matches; the Trie keeps the same worst-case time but trades extra memory for fewer redundant substring lookups on long inputs.
Constraints
- 1 <= len(s) <= 300 (an empty s returns True)
- 1 <= word_dict.length <= 1000 (an empty dictionary is allowed; only the empty string is then segmentable)
- 1 <= each word length <= 20
- s and all dictionary words consist of lowercase English letters
- Dictionary words may be reused any number of times
Examples
Input: ("leetcode", ["leet", "code"])
Expected Output: True
Explanation: "leet" + "code" covers the whole string.
Input: ("applepenapple", ["apple", "pen"])
Expected Output: True
Explanation: "apple" + "pen" + "apple"; the word "apple" is reused.
Hints
- Define dp[i] = True iff the prefix s[:i] can be segmented. dp[0] = True because the empty prefix is trivially segmentable.
- For each end index i, look back to a split point j: if dp[j] is True and s[j:i] is a dictionary word, then dp[i] is True.
- Put the dictionary in a hash set for O(1) membership, and bound the inner loop by the longest word length so you never test substrings longer than any dictionary word.
- For the Trie variant, walk the Trie from each start position; stop the inner scan as soon as no child matches the next character (early termination), which speeds up long inputs with few matching prefixes.