How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: ("catsandog", ["cats", "dog", "sand", "and", "cat"])

Expected Output: []

Explanation: No combination of dictionary words covers the whole string (the trailing 'og' cannot be formed), so an empty list is returned.

Input: ("aaaa", ["a", "aa"])

Expected Output: ["aa", "aa"]

Explanation: Multiple decompositions exist; the solution returns one valid split. "aa" + "aa" covers "aaaa".

Input: ("a", ["a"])

Expected Output: ["a"]

Explanation: Single-character string equal to a single dictionary word.

Input: ("b", ["a"])

Expected Output: []

Explanation: 'b' is not in the dictionary, so it cannot be built; empty list.

Input: ("abcd", ["ab", "cd", "abc", "d"])

Expected Output: ["ab", "cd"]

Explanation: Although 'abc' + 'd' is also valid, the solution returns one valid decomposition: 'ab' + 'cd'.

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.

Quick Overview

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.