Construct String with Minimum Cost (Easy) - Solution & Explanation

Problem Overview: You are given a target string and a list of words where each word has an associated cost. The task is to construct the target by concatenating words from the list while minimizing the total cost. Words can only match the target at valid positions, so the core challenge is choosing the cheapest sequence of matches that fully builds the string.

Approach 1: Brute Force Backtracking (Exponential Time, O(2^n) time, O(n) space)

The most direct idea is to try constructing the target from left to right. At every index, iterate through every word and check whether it matches the substring starting at that position. If it matches, recursively attempt to build the rest of the string and add the word's cost. This explores every possible combination of word placements. While conceptually simple, repeated exploration of the same suffix makes this approach exponential and impractical for larger inputs.

Approach 2: Dynamic Programming with Substring Checks (O(n * m * L) time, O(n) space)

Dynamic programming avoids recomputation by storing the minimum cost needed to construct the suffix starting at each index. For position i, iterate over all words and check whether each word matches the substring starting at i. If it does, update dp[i] using cost(word) + dp[i + len(word)]. This eliminates repeated work compared to brute force, but still performs many substring comparisons, especially when the word list is large.

Approach 3: Trie + Memoized DFS (Optimal) (O(n * L) time, O(n + totalTrieNodes) space)

The optimized solution stores all words in a Trie. Starting from each index of the target, traverse the Trie character by character while simultaneously scanning the string. Every time a Trie node marks the end of a word, treat it as a valid cut and recursively compute the cost for the remaining suffix. Use memoization to cache the minimum cost for each starting index so each suffix is solved once. Trie traversal avoids checking every word individually and only follows characters that actually match the target. The recursion behaves like a DFS over valid word boundaries while memoization guarantees efficiency.

Recommended for interviews: The Trie + memoized DFS approach is the expected solution. Brute force demonstrates the baseline idea of exploring word placements, but the optimal approach shows you understand prefix structures and dynamic programming to eliminate redundant work. Interviewers typically look for recognizing overlapping subproblems and using a Trie to efficiently match prefixes.