Determine string buildability from dictionary

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.

Determine String Buildability from Dictionary (Word Break with Reconstruction)

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

Hints

1. Use dynamic programming over prefixes: let reachable[i] mean s[:i] can be segmented into dictionary words. reachable[0] is True (empty prefix).
2. 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.
3. 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.
4. Put the dictionary in a hash set for O(L) average-time membership checks; precompute the max word length to limit the inner loop.