Solution

Method 1 – Dynamic Programming (Substring Matching)

Intuition

We want to build the target string by appending words from the list, minimizing the total cost. Since the constraints are small, we can use a simple DP where for each position, we check all words that could end at that position and update the minimum cost.

Approach

Let dp[i] be the minimum cost to build target[:i]. Initialize dp[0] = 0, others to infinity.
For each position i in target (1 to n):
- For each word, if

Related Tags