Determine string buildability from dictionary
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a non-empty string s and a list of non-empty words dict, determine whether s can be formed by concatenating words from dict with unlimited reuse allowed. If possible, return one valid decomposition as a list of words in order; otherwise, return an empty list. Implement an efficient solution and analyze its time and space complexity, considering very long s and large dictionaries.
Quick Answer: This question evaluates understanding of string manipulation, algorithm design for combinatorial search, dynamic programming/memoization concepts, and the ability to analyze time and space complexity.
Given a non-empty string `s` and a list of non-empty words `words` (a dictionary), determine whether `s` can be formed by concatenating words from `words`, with unlimited reuse of each word allowed.
If it is possible, return ONE valid decomposition as a list of words in order (any valid decomposition is accepted). If it is not possible, return an empty list.
Aim for an efficient solution that scales to very long `s` and large dictionaries.
Examples:
- `s = "leetcode"`, `words = ["leet", "code"]` -> `["leet", "code"]`
- `s = "applepenapple"`, `words = ["apple", "pen"]` -> `["apple", "pen", "apple"]`
- `s = "catsandog"`, `words = ["cats", "dog", "sand", "and", "cat"]` -> `[]` (cannot be segmented)
Note: When multiple decompositions exist, returning any one of them is correct.
Constraints
- 1 <= len(s) <= 10^4
- 1 <= len(words) <= 10^4
- 1 <= len(word) <= 100 for each word in words
- s and all words consist of lowercase English letters
- Each word may be reused an unlimited number of times
- If multiple valid decompositions exist, any one is accepted
Examples
Input: ("leetcode", ["leet", "code"])
Expected Output: ["leet", "code"]
Explanation: "leetcode" splits cleanly into "leet" + "code", both in the dictionary.
Input: ("applepenapple", ["apple", "pen"])
Expected Output: ["apple", "pen", "apple"]
Explanation: "apple" is reused; decomposition is apple + pen + apple.
Hints
- Use dynamic programming over prefixes: let reachable[i] mean s[:i] can be segmented into dictionary words. reachable[0] is True (empty prefix).
- For each end index i, look back to a start index j where reachable[j] is True and s[j:i] is in the dictionary. Bound j by the maximum word length so you don't scan the whole prefix.
- To reconstruct the actual decomposition, store the chosen split point (choice[i] = j) for each reachable i, then walk backwards from n to 0 and reverse the collected words.
- Put the dictionary in a hash set for O(L) average-time membership checks; precompute the max word length to limit the inner loop.