Problem Description

You are given a string target that you need to construct, along with an array of strings words and an array of integers costs (both arrays have the same length).

Starting with an empty string s, you can perform the following operation any number of times (including zero times):

• Choose any index i from the range [0, words.length - 1]
• Append words[i] to the end of string s
• This operation costs costs[i]

Your goal is to find the minimum total cost to make string s equal to the target string. If it's impossible to construct the target string using the given words, return -1.

For example, if target = "abcd", words = ["ab", "cd", "abcd"], and costs = [3, 2, 5], you could:

• Use words[0] ("ab") with cost 3, then words[1] ("cd") with cost 2, for a total cost of 5
• Or use words[2] ("abcd") directly with cost 5
• The minimum cost would be 5

The key insight is that you can use any word from the words array multiple times, and the words must be appended in sequence to form the exact target string.

Intuition

To construct the target string optimally, we need to make decisions at each position: which word from our available words should we use next? This naturally leads to a dynamic programming approach where we try different words starting from each position.

The key observation is that at any position i in the target string, we need to find all possible words that can match starting from that position. For instance, if we're at position i and we have words that match target[i:i+2], target[i:i+3], and target[i:i+5], we need to try all of them and pick the one that gives us the minimum total cost.

However, checking every word against every position would be inefficient. This is where a Trie (prefix tree) becomes invaluable. By storing all words in a Trie, we can efficiently find all words that match starting from any position in the target string. As we traverse the target string from position i, we simultaneously traverse the Trie. If at any point the Trie path doesn't exist, we know no word can match beyond that point.

The problem then becomes: for each position i in the target string, we explore all possible words that can start from position i by traversing the Trie. For each valid word found (reaching a node in Trie that marks the end of a word), we have two pieces of information:

1. The cost of using this word (stored in the Trie node)
2. The next position we need to solve (which is j+1 where j is the ending position of the current word)

This recursive structure naturally fits memoization: dfs(i) represents "what's the minimum cost to construct the target string starting from position i?" The answer would be the minimum among all valid words starting at position i, where each choice costs word_cost + dfs(next_position).

The Trie optimization is crucial here - instead of checking all words at each position (which could be expensive), we traverse the Trie character by character, pruning impossible paths early and finding all matching words in a single traversal.

Solution Approach

The solution uses a Trie data structure combined with memoized depth-first search to efficiently find the minimum cost.

Building the Trie

First, we create a Trie where each node contains:

• An array children of length 26 (for lowercase English letters)
• A cost variable storing the minimum cost to reach this node from the root

We insert each word from the words array into the Trie:

def insert(self, word: str, cost: int):
    node = self
    for c in word:
        idx = ord(c) - ord("a")
        if node.children[idx] is None:
            node.children[idx] = Trie()
        node = node.children[idx]
    node.cost = min(node.cost, cost)

The key detail is that if multiple words end at the same node, we keep only the minimum cost using min(node.cost, cost).

Memoized Search Function

The core algorithm is the recursive function dfs(i) which returns the minimum cost to construct target[i:] (the substring starting from index i):

@cache
def dfs(i: int) -> int:
    if i >= len(target):
        return 0  # Base case: entire string constructed
  
    ans = inf
    node = trie
    for j in range(i, len(target)):
        idx = ord(target[j]) - ord("a")
        if node.children[idx] is None:
            return ans  # No more matching words possible
        node = node.children[idx]
        ans = min(ans, node.cost + dfs(j + 1))
    return ans

The function works as follows:

1. Base Case: If i >= len(target), we've successfully constructed the entire target string, so return 0.

2. Trie Traversal: Starting from the root of the Trie and position i in the target:

   • For each character target[j] where j goes from i to the end of target
   • Check if the Trie has a child node for this character
   • If not, break early (no word can match beyond this point)
   • If yes, move to that child node

3. Cost Calculation: At each valid node in the Trie that represents the end of a word (where node.cost < inf):

   • Calculate the total cost as: node.cost (cost of current word) + dfs(j + 1) (minimum cost for the remaining string)
   • Keep track of the minimum cost among all possibilities

4. Memoization: The @cache decorator ensures that dfs(i) is computed only once for each unique value of i, avoiding redundant calculations.

Final Result

The answer is dfs(0) - the minimum cost to construct the entire target string starting from position 0. If this value is still inf, it means the target cannot be constructed, so we return -1.

The time complexity is O(n * m + n^2) where n is the length of the target string and m is the total length of all words (for Trie construction). The space complexity is O(n + m) for the recursion stack, memoization cache, and Trie storage.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• target = "abcd"
• words = ["ab", "bc", "cd", "abcd"]
• costs = [2, 3, 1, 5]

Step 1: Build the Trie

We insert each word with its cost into the Trie:

Root
├── a
│   └── b (cost=2)
│       └── c
│           └── d (cost=5)
├── b
│   └── c (cost=3)
└── c
    └── d (cost=1)

Step 2: Execute DFS with Memoization

Starting with dfs(0) (constructing from position 0):

At position 0, we traverse the Trie starting from root while matching with target[0:] = "abcd":

• Match 'a': Move to node 'a' in Trie ✓
• Match 'b': Move to node 'b' under 'a' ✓ (Found word "ab" with cost=2)
  • Option 1: Use "ab" (cost=2) and solve for dfs(2)
• Match 'c': Move to node 'c' under 'b' ✓
• Match 'd': Move to node 'd' under 'c' ✓ (Found word "abcd" with cost=5)
  • Option 2: Use "abcd" (cost=5) and solve for dfs(4)

For Option 1: Cost = 2 + dfs(2)

• At dfs(2), we start matching from position 2 ("cd"):
  • Match 'c': Move to node 'c' in Trie ✓
  • Match 'd': Move to node 'd' under 'c' ✓ (Found word "cd" with cost=1)
    • Use "cd" (cost=1) and solve for dfs(4)
  • dfs(4) returns 0 (base case: reached end of target)
  • So dfs(2) = 1 + 0 = 1
• Total for Option 1: 2 + 1 = 3

For Option 2: Cost = 5 + dfs(4)

• dfs(4) returns 0 (base case)
• Total for Option 2: 5 + 0 = 5

Therefore, dfs(0) = min(3, 5) = 3

Step 3: Return Result

The minimum cost to construct "abcd" is 3, achieved by using:

• "ab" (cost=2) at position 0
• "cd" (cost=1) at position 2

Note how the Trie helped us efficiently find all valid words starting at each position without checking every word in the array, and memoization ensured we only computed dfs(4) once even though it was needed in multiple paths.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2 + L)

The time complexity consists of two main components:

• Building the Trie: O(L) where L is the sum of lengths of all words in the words array. Each character of every word is processed once during insertion.
• DFS with memoization: O(n^2) where n is the length of target. The dfs function can be called at most n times (once for each starting position in target). For each call to dfs(i), the inner loop iterates from position i to the end of target, which takes O(n) time in the worst case. Since we use @cache decorator for memoization, each state i is computed only once. Therefore, the total time for all DFS calls is O(n) * O(n) = O(n^2).

Space Complexity: O(n + L)

The space complexity consists of:

• Trie structure: O(L) to store all characters of all words. In the worst case, if all words have completely different characters, we need space proportional to the total number of characters.
• Memoization cache: O(n) to store the results for each starting position in target.
• Recursion call stack: O(n) in the worst case when the recursion depth equals the length of target.

Since the recursion stack and memoization cache both contribute O(n), and the Trie contributes O(L), the total space complexity is O(n + L).

Common Pitfalls

1. Not Handling Word Reuse Properly

A common mistake is assuming each word can only be used once. The problem allows using the same word multiple times.

Incorrect Approach:

# Wrong: Marking words as "used"
used = [False] * len(words)
def dfs(i):
    for word_idx, word in enumerate(words):
        if not used[word_idx]:  # Wrong! Words can be reused
            used[word_idx] = True
            # ... try to use word
            used[word_idx] = False

Correct Approach: The provided solution correctly allows word reuse by not tracking usage state.

2. Inefficient String Matching Without Trie

Many solutions attempt to check every word at every position, leading to redundant comparisons.

Inefficient Approach:

def dfs(i):
    if i >= len(target):
        return 0
  
    min_cost = inf
    for idx, word in enumerate(words):
        # This checks the entire word every time - O(word_length)
        if target[i:].startswith(word):
            min_cost = min(min_cost, costs[idx] + dfs(i + len(word)))
    return min_cost

This approach has worse time complexity because:

• It checks every word at every position
• String slicing and startswith() are expensive operations
• No early termination when no words can match

Efficient Solution with Trie: The Trie approach allows:

• Early termination when no words can match (when node.children[idx] is None)
• Incremental matching character by character
• Sharing common prefixes between words

3. Not Updating Minimum Cost for Duplicate Words

If multiple words are identical but have different costs, failing to keep only the minimum cost leads to suboptimal solutions.

Wrong Implementation:

def insert(self, word: str, cost: int):
    node = self
    for c in word:
        idx = ord(c) - ord("a")
        if node.children[idx] is None:
            node.children[idx] = Trie()
        node = node.children[idx]
    node.cost = cost  # Wrong! Should be min(node.cost, cost)

Correct Implementation:

node.cost = min(node.cost, cost)  # Keep only the minimum cost

4. Forgetting to Initialize Cost as Infinity

Not initializing the cost field properly in the Trie node can cause incorrect minimum calculations.

Wrong:

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.cost = 0  # Wrong! Should be inf

Correct:

self.cost = inf  # Properly initialized to infinity

This ensures that only explicitly set costs are considered valid, and unset nodes don't interfere with minimum calculations.

5. Missing Base Case or Incorrect Return Value

Forgetting the base case or returning the wrong value when target cannot be constructed.

Common Mistakes:

# Missing base case
def dfs(i):
    # Forgot: if i >= len(target): return 0
    min_cost = inf
    # ... rest of logic
  
# Wrong return value for impossible case
result = dfs(0)
return result  # Should check if result is inf and return -1

Correct Handling:

return result if result < inf else -1