Facebook Pixel

3253. Construct String with Minimum Cost (Easy) 🔒

Medium
Leetcode Link

Problem Description

You are given a string target, an array of strings words, and an integer array costs, both arrays of the same length.

Imagine an empty string s.

You can perform the following operation any number of times (including zero):

  • Choose an index i in the range [0, words.length - 1].
  • Append words[i] to s.
  • The cost of operation is costs[i].

Return the minimum cost to make s equal to target. If it's not possible, return -1.

Intuition

The problem essentially requires constructing the target string using the given words with an associated costs array, ensuring the total construction cost is minimized. At its core, this is a search problem where the challenge lies in efficiently exploring potential word placements that build up the target.

Solution Approach

  1. Trie Data Structure: The solution uses a Trie to efficiently store the words and their respective costs. Each node in the Trie corresponds to a letter and maintains a cost variable, representing the minimal cost to form that sequence starting from the root node.

  2. Inserting Words into Trie: As you insert words into the Trie, update the cost at each node. If multiple words reach the same node, retain the smallest cost since you want to minimize costs while forming parts of the target.

  3. Memoized Search (DFS): To calculate the minimum cost to form the target, use a depth-first search aided by memoization. This DFS explores all suffixes starting from a given position in target.

    • Base Case: If the starting position i reaches beyond the length of target, no additional cost is needed, thus returning 0.

    • Recursive Exploration: Start from the root of the Trie and attempt to map the remaining characters of target to words in the Trie. For each valid match (from target[i] to some target[j] corresponding to a word in words), compute the potential cost and solve the subproblem for the suffix starting at target[j + 1].

  4. Result Calculation: The outcome is determined by the minimum cost obtained from dfs(0). If dfs(0) is less than infinity, it indicates a valid formation of target; otherwise, return -1.

By organizing words in a Trie and leveraging memoization for exploring target formations, the solution optimizes decisions on cost-efficient word combinations to form the desired target string.

Solution Approach

To solve this problem, we use a Trie data structure combined with a memoized depth-first search (DFS) approach. Here’s a step-by-step breakdown of the implementation and the algorithms involved:

  1. Trie Construction:

    • We define a Trie class where each node contains an array children of size 26 (for each lowercase English letter) and a variable cost to track the minimal cost to reach that node.
    • For each word in words along with its corresponding cost from costs, we insert the word into the Trie:
      • Begin at the root and iterate through the characters in the word.
      • For each character, calculate its index (idx) using the formula ord(c) - ord("a").
      • If the respective child node doesn't exist, create it.
      • Move to the child node and update its cost with the minimum of the existing cost and the current cost of insertion.

  2. Memoized DFS:

    • Define a recursive method dfs(i), which calculates the minimum cost to build target[i:] (the substring starting from index i).
    • Base case: If i exceeds the length of target, return 0 since no cost is needed for an empty suffix.
    • Begin at the Trie's root for each new call and try to form substrings of target starting from position i.
    • Traverse characters in target from i onward:
      • Calculate the index idx for the current character.
      • If the respective node in the Trie is null, exit early, as further matching is impossible.
      • Move to the child node, and use its cost combined with dfs(j + 1) (for the remaining suffix) to update the minimum cost ans.
    • By caching results of dfs(i), redundant calculations are avoided, enabling efficient exploration of all possible combinations.

  3. Result Retrieval:

    • Call dfs(0) to calculate the minimum cost to form target from scratch.
    • If the result is less than infinity, return it as the answer. Otherwise, return -1, indicating that constructing target using the given words isn't feasible.

In essence, this solution combines Trie data structure's efficiency in prefix matching with memoized DFS to explore possible constructions systematically, ensuring minimum cost is achieved.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have the following input:

  • target = "abac"
  • words = ["ab", "bac", "a"]
  • costs = [1, 2, 1]

We'll walk through how we can use the given solution approach to determine the minimum cost to construct target.

  1. Trie Construction:

    • Initialize an empty Trie.
    • Insert the word "ab" with cost 1:
      • Insert 'a' at the root with cost 1.
      • Append 'b' with cost 1.
    • Insert the word "bac" with cost 2:
      • Insert 'b' at the root with cost 2 since no overlapping 'b' with a lower cost is present.
      • Append 'a' with cost 2.
      • Append 'c' with cost 2.
    • Insert the word "a" with cost 1:
      • The node for 'a' already exists, ensure its cost is still the smallest, i.e., min(1, 1).

  2. Memoized DFS:

    • Start the DFS from index 0 of target = "abac".
    • At i = 0, match "ab" (from Trie) with cost 1. Recursive DFS for target[2:] = "ac".
    • At i = 2, match "a" (from Trie) with cost 1. Recursive DFS for target[3:] = "c".
    • At i = 3, match "c" is not possible, thus return infinite cost.
    • Backtrack and try "bac" from i = 0 directly with cost 2, reaching target[3:] = "c", again unraveled leads to infinite cost.
    • Final combination: "ab" (cost 1) then "a" (cost 1) from the Trie.

  3. Result Calculation:

    • The minimum cost found is 2 (from "ab" + "a"), with memoization preventing redundant DFS calls.
    • Therefore, the minimum cost to form target using words is 2.

In this example, using Trie and DFS search efficiently, we found that the target string "abac" can be constructed at a minimum cost of 2 by using the words "ab" and "a".

Solution Implementation

1from functools import cache
2from typing import List, Optional
3import sys
4
5# Use an arbitrarily large number to represent infinity
6inf = sys.maxsize
7
8class Trie:
9    def __init__(self):
10        # Initialize each Trie node with an array of 26 None elements for storing child nodes
11        self.children: List[Optional[Trie]] = [None] * 26
12        # Set the initial cost of reaching this node to infinity
13        self.cost = inf
14
15    def insert(self, word: str, cost: int):
16        node = self
17        # Traverse the trie while inserting each character of the word
18        for char in word:
19            index = ord(char) - ord('a')
20            if node.children[index] is None:
21                # Create a new Trie node if it does not exist
22                node.children[index] = Trie()
23            node = node.children[index]
24        # Store the minimum cost to reach the end of this word
25        node.cost = min(node.cost, cost)
26
27class Solution:
28    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
29        @cache
30        def dfs(index: int) -> int:
31            # Base case: When index exceeds target length, return zero cost
32            if index >= len(target):
33                return 0
34          
35            # Initialize the minimum cost as infinity
36            min_cost = inf
37            node = trie
38            # Try to form the target string from current position
39            for j in range(index, len(target)):
40                idx = ord(target[j]) - ord('a')
41                if node.children[idx] is None:
42                    # Cannot proceed if there is no such character path in the trie
43                    return min_cost
44                node = node.children[idx]
45                # Update the minimum cost by selecting the path with the current node's cost
46                min_cost = min(min_cost, node.cost + dfs(j + 1))
47            return min_cost
48
49        # Construct the Trie with given words and costs
50        trie = Trie()
51        for word, cost in zip(words, costs):
52            trie.insert(word, cost)
53      
54        result = dfs(0)
55        # Return the minimum cost found, or -1 if not possible
56        return result if result < inf else -1
57
1// Trie class to store words and their associated costs
2class Trie {
3    public static final int INF = 1 << 29; // A large number representing infinity
4    public Trie[] children = new Trie[26]; // Array to store references to child nodes
5    public int cost = INF; // Cost to reach this node, initialized to INF
6
7    // Method to insert a word with its cost into the Trie
8    public void insert(String word, int cost) {
9        Trie node = this; // Start from the root of the Trie
10        for (char c : word.toCharArray()) { // Iterate over each character in the word
11            int index = c - 'a'; // Map character to an index (0-25)
12            if (node.children[index] == null) {
13                node.children[index] = new Trie(); // Create a new Trie node if none exists
14            }
15            node = node.children[index]; // Move to the child node
16        }
17        node.cost = Math.min(node.cost, cost); // Update the cost at the node if a cheaper cost is found
18    }
19}
20
21// Solution class to solve the problem of finding the minimum transformation cost
22class Solution {
23    private Trie trie = new Trie(); // Trie to store words and their associated costs
24    private char[] target; // Character array of the target word
25    private Integer[] f; // Memoization array to store results of subproblems
26
27    // Main method to calculate minimum cost to form the target using given words
28    public int minimumCost(String target, String[] words, int[] costs) {
29        for (int i = 0; i < words.length; ++i) { // Insert each word into the Trie
30            trie.insert(words[i], costs[i]);
31        }
32        this.target = target.toCharArray(); // Convert target String to character array
33        f = new Integer[target.length()]; // Initialize memoization array
34        int ans = dfs(0); // Start Depth First Search from index 0
35        return ans < trie.INF ? ans : -1; // Return result; if INF, return -1 indicating impossible
36    }
37
38    // Depth First Search method to find minimum cost starting from index i
39    private int dfs(int i) {
40        if (i >= target.length) { // Base case: if reached the end of target, return 0
41            return 0;
42        }
43        if (f[i] != null) { // Check if result for this subproblem is already computed
44            return f[i]; // Return the memoized result
45        }
46        f[i] = trie.INF; // Initialize result to INF
47        Trie node = trie; // Start from the root of the Trie
48        for (int j = i; j < target.length; ++j) { // Iterate from current index to the end of target
49            int index = target[j] - 'a'; // Map character to an index
50            if (node.children[index] == null) { // If no child exists for this character, stop
51                return f[i];
52            }
53            node = node.children[index]; // Move to the child node
54            // Update result with minimum cost of splitting the target at position j
55            f[i] = Math.min(f[i], node.cost + dfs(j + 1));
56        }
57        return f[i]; // Return minimum cost for current starting index
58    }
59}
60
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <cstring>
6
7using namespace std;
8
9const int INF = 1 << 29;
10
11class Trie {
12public:
13    Trie* children[26]{}; // Array to hold pointers to the child Trie nodes
14    int cost = INF;        // Cost value initialized to a large number
15
16    // Function to insert a word and its associated cost into the Trie
17    void insert(string& word, int cost) {
18        Trie* node = this;
19        for (char c : word) {
20            int idx = c - 'a'; // Calculate index for character 'a' as 0, 'b' as 1, etc.
21            if (!node->children[idx]) {
22                node->children[idx] = new Trie(); // Create a new Trie node if it doesn't exist
23            }
24            node = node->children[idx]; // Move to the newly created or existing node
25        }
26        node->cost = min(node->cost, cost); // Update the cost of the node with the minimum cost
27    }
28};
29
30class Solution {
31public:
32    // Function to find the minimum cost to construct the target string using given words and respective costs
33    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
34        Trie* trie = new Trie(); // Create a new Trie
35        for (int i = 0; i < words.size(); ++i) {
36            trie->insert(words[i], costs[i]); // Insert each word and its cost into the Trie
37        }
38      
39        int n = target.length();
40        int dp[n]; // Create a dynamic programming array for memoization
41        memset(dp, 0, sizeof(dp)); // Initialize the array with zeros
42
43        // Lambda function for recursive depth-first search with memoization
44        auto dfs = [&](auto&& self, int i) -> int {
45            if (i >= n) {
46                return 0; // Base case: If index exceeds target length, return cost 0
47            }
48            if (dp[i]) {
49                return dp[i]; // Return memoized value if already calculated
50            }
51            dp[i] = INF; // Initialize the current position with a large cost
52
53            Trie* node = trie;
54            for (int j = i; j < n; ++j) {
55                int idx = target[j] - 'a'; // Determine the index for character in the Trie
56                if (!node->children[idx]) {
57                    return dp[i]; // If no further path, return current dp[i]
58                }
59                node = node->children[idx]; // Move to the next node
60                // Calculate the minimum cost dynamically
61                dp[i] = min(dp[i], node->cost + self(self, j + 1));
62            }
63            return dp[i];
64        };
65
66        int ans = dfs(dfs, 0);
67        return ans < INF ? ans : -1; // Return the answer. If INF, it means no solution was found.
68    }
69};
70
1const INF = 1 << 29;
2
3// Represents a single node in a Trie
4interface TrieNode {
5    children: (TrieNode | null)[];
6    cost: number;
7}
8
9// Initializes a new Trie node
10function createTrieNode(): TrieNode {
11    return { children: Array(26).fill(null), cost: INF };
12}
13
14// Inserts a word with its associated cost into the Trie
15function insert(trie: TrieNode, word: string, cost: number): void {
16    let node = trie;
17    for (const char of word) {
18        const idx = char.charCodeAt(0) - 97; // Calculate index for each character
19        if (!node.children[idx]) {
20            node.children[idx] = createTrieNode(); // Create a new node if needed
21        }
22        node = node.children[idx]!;
23    }
24    node.cost = Math.min(node.cost, cost); // Update the cost of the node
25}
26
27// Calculates the minimum cost to construct the target string
28function minimumCost(target: string, words: string[], costs: number[]): number {
29    const trie = createTrieNode();
30
31    // Insert each word with its cost into the Trie
32    for (let i = 0; i < words.length; ++i) {
33        insert(trie, words[i], costs[i]);
34    }
35
36    const n = target.length;
37    const memo: number[] = Array(n).fill(0);
38
39    // Depth-First Search function to determine the minimum cost
40    const dfs = (index: number): number => {
41        if (index >= n) {
42            return 0; // Base case: If at the end of the target string, cost is zero
43        }
44        if (memo[index]) {
45            return memo[index]; // Return cached result if already calculated
46        }
47        memo[index] = INF; // Initialize the current position's cost to INF
48        let node: TrieNode | null = trie;
49
50        // Explore each character from the current position onwards
51        for (let j = index; j < n; ++j) {
52            const idx = target.charCodeAt(j) - 97;
53            if (!node?.children[idx]) {
54                return memo[index]; // If no matching character in Trie, stop exploration
55            }
56            node = node.children[idx];
57            memo[index] = Math.min(memo[index], node!.cost + dfs(j + 1)); // Update the minimum cost
58        }
59        return memo[index];
60    };
61
62    const result = dfs(0);
63    return result < INF ? result : -1; // Return result or -1 if target is not constructible
64}
65

Time and Space Complexity

The time complexity of the given code is O(n^2 + L), where n is the length of the target string, and L is the sum of the lengths of all words in the words array.

  • The insert operation for each word contributes to a complexity of O(L) as each word is inserted into the trie, resulting in a total complexity of O(L) for all words.
  • The dfs function, which is memoized, iterates over ranges of the target string, resulting in a complexity of O(n^2).

The space complexity is O(n + L):

  • The dfs function uses memoization, contributing to a space requirement of O(n) due to caching results for each position in the target string.
  • The trie structure itself requires space proportional to O(L) to store the nodes for each character in all words.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More