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.
