Welcome to Subscribe On Youtube

3253. Construct String with Minimum Cost (Easy) 🔒

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.

 

Example 1:

Input: target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

Output: 7

Explanation:

The minimum cost can be achieved by performing the following operations:

• Select index 1 and append "abc" to s at a cost of 1, resulting in s = "abc".
• Select index 2 and append "d" to s at a cost of 1, resulting in s = "abcd".
• Select index 4 and append "ef" to s at a cost of 5, resulting in s = "abcdef".

Example 2:

Input: target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

Output: -1

Explanation:

It is impossible to make s equal to target, so we return -1.

 

Constraints:

• 1 <= target.length <= 2000
• 1 <= words.length == costs.length <= 50
• 1 <= words[i].length <= target.length
• target and words[i] consist only of lowercase English letters.
• 1 <= costs[i] <= 105

Solutions

Solution 1: Trie + Memoized Search

We first create a Trie $\mathit{\text{trie}}$, where each node in the Trie contains an array $\mathit{\text{children}}$ of length $26$, and each element in the array is a pointer to the next node. Each node in the Trie also contains a $\mathit{\text{cost}}$ variable, which represents the minimum cost from the root node to the current node.

We traverse the $\mathit{\text{words}}$ array, inserting each word into the Trie while updating the $\mathit{\text{cost}}$ variable for each node.

Next, we define a memoized search function $\mathit{\text{dfs}}(i)$, which represents the minimum cost to construct the string starting from $\mathit{\text{target}}[i]$. The answer is $\mathit{\text{dfs}}(0)$.

The calculation process of the function $\mathit{\text{dfs}}(i)$ is as follows:

• If $i\ge \mathit{\text{len}}(\mathit{\text{target}})$, it means the entire string has been constructed, so return $0$.
• Otherwise, we start from the root node of the $\mathit{\text{trie}}$ and traverse all suffixes starting from $\mathit{\text{target}}[i]$, finding the minimum cost, which is the $\mathit{\text{cost}}$ variable in the $\mathit{\text{trie}}$, plus the result of $\mathit{\text{dfs}}(j+1)$, where $j$ is the ending position of the suffix starting from $\mathit{\text{target}}[i]$.

Finally, if $\mathit{\text{dfs}}(0)<\mathit{\text{inf}}$, return $\mathit{\text{dfs}}(0)$; otherwise, return $-1$.

The time complexity is $O(n^2+L)$, and the space complexity is $O(n+L)$. Here, $n$ is the length of $\mathit{\text{target}}$, and $L$ is the sum of the lengths of all words in the $\mathit{\text{words}}$ array.

• Java
• C++
• Python
• Go
• TypeScript

• class Trie {
      public final int inf = 1 << 29;
      public Trie[] children = new Trie[26];
      public int cost = inf;
  
      public void insert(String word, int cost) {
          Trie node = this;
          for (char c : word.toCharArray()) {
              int idx = c - 'a';
              if (node.children[idx] == null) {
                  node.children[idx] = new Trie();
              }
              node = node.children[idx];
          }
          node.cost = Math.min(node.cost, cost);
      }
  }
  
  class Solution {
      private Trie trie = new Trie();
      private char[] target;
      private Integer[] f;
  
      public int minimumCost(String target, String[] words, int[] costs) {
          for (int i = 0; i < words.length; ++i) {
              trie.insert(words[i], costs[i]);
          }
          this.target = target.toCharArray();
          f = new Integer[target.length()];
          int ans = dfs(0);
          return ans < trie.inf ? ans : -1;
      }
  
      private int dfs(int i) {
          if (i >= target.length) {
              return 0;
          }
          if (f[i] != null) {
              return f[i];
          }
          f[i] = trie.inf;
          Trie node = trie;
          for (int j = i; j < target.length; ++j) {
              int idx = target[j] - 'a';
              if (node.children[idx] == null) {
                  return f[i];
              }
              node = node.children[idx];
              f[i] = Math.min(f[i], node.cost + dfs(j + 1));
          }
          return f[i];
      }
  }
  
  

• const int inf = 1 << 29;
  
  class Trie {
  public:
      Trie* children[26]{};
      int cost = inf;
  
      void insert(string& word, int cost) {
          Trie* node = this;
          for (char c : word) {
              int idx = c - 'a';
              if (!node->children[idx]) {
                  node->children[idx] = new Trie();
              }
              node = node->children[idx];
          }
          node->cost = min(node->cost, cost);
      }
  };
  
  class Solution {
  public:
      int minimumCost(string target, vector<string>& words, vector<int>& costs) {
          Trie* trie = new Trie();
          for (int i = 0; i < words.size(); ++i) {
              trie->insert(words[i], costs[i]);
          }
          int n = target.length();
          int f[n];
          memset(f, 0, sizeof(f));
          auto dfs = [&](auto&& dfs, int i) -> int {
              if (i >= n) {
                  return 0;
              }
              if (f[i]) {
                  return f[i];
              }
              f[i] = inf;
              Trie* node = trie;
              for (int j = i; j < n; ++j) {
                  int idx = target[j] - 'a';
                  if (!node->children[idx]) {
                      return f[i];
                  }
                  node = node->children[idx];
                  f[i] = min(f[i], node->cost + dfs(dfs, j + 1));
              }
              return f[i];
          };
          int ans = dfs(dfs, 0);
          return ans < inf ? ans : -1;
      }
  };
  
  

• class Trie:
      def __init__(self):
          self.children: List[Optional[Trie]] = [None] * 26
          self.cost = inf
  
      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)
  
  
  class Solution:
      def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
          @cache
          def dfs(i: int) -> int:
              if i >= len(target):
                  return 0
              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
                  node = node.children[idx]
                  ans = min(ans, node.cost + dfs(j + 1))
              return ans
  
          trie = Trie()
          for word, cost in zip(words, costs):
              trie.insert(word, cost)
          ans = dfs(0)
          return ans if ans < inf else -1
  
  

• const inf = 1 << 29
  
  type Trie struct {
  	children [26]*Trie
  	cost     int
  }
  
  func NewTrie() *Trie {
  	return &Trie{cost: inf}
  }
  
  func (t *Trie) insert(word string, cost int) {
  	node := t
  	for _, c := range word {
  		idx := c - 'a'
  		if node.children[idx] == nil {
  			node.children[idx] = NewTrie()
  		}
  		node = node.children[idx]
  	}
  	node.cost = min(node.cost, cost)
  }
  
  func minimumCost(target string, words []string, costs []int) int {
  	trie := NewTrie()
  	for i, word := range words {
  		trie.insert(word, costs[i])
  	}
  
  	n := len(target)
  	f := make([]int, n)
  	var dfs func(int) int
  	dfs = func(i int) int {
  		if i >= n {
  			return 0
  		}
  		if f[i] != 0 {
  			return f[i]
  		}
  		f[i] = inf
  		node := trie
  		for j := i; j < n; j++ {
  			idx := target[j] - 'a'
  			if node.children[idx] == nil {
  				return f[i]
  			}
  			node = node.children[idx]
  			f[i] = min(f[i], node.cost+dfs(j+1))
  		}
  		return f[i]
  	}
  	if ans := dfs(0); ans < inf {
  		return ans
  	}
  	return -1
  }
  
  

• const inf = 1 << 29;
  
  class Trie {
      children: (Trie | null)[];
      cost: number;
  
      constructor() {
          this.children = Array(26).fill(null);
          this.cost = inf;
      }
  
      insert(word: string, cost: number): void {
          let node: Trie = this;
          for (const c of word) {
              const idx = c.charCodeAt(0) - 97;
              if (!node.children[idx]) {
                  node.children[idx] = new Trie();
              }
              node = node.children[idx]!;
          }
          node.cost = Math.min(node.cost, cost);
      }
  }
  
  function minimumCost(target: string, words: string[], costs: number[]): number {
      const trie = new Trie();
      for (let i = 0; i < words.length; ++i) {
          trie.insert(words[i], costs[i]);
      }
  
      const n = target.length;
      const f: number[] = Array(n).fill(0);
      const dfs = (i: number): number => {
          if (i >= n) {
              return 0;
          }
          if (f[i]) {
              return f[i];
          }
          f[i] = inf;
          let node: Trie | null = trie;
          for (let j = i; j < n; ++j) {
              const idx = target.charCodeAt(j) - 97;
              if (!node?.children[idx]) {
                  return f[i];
              }
              node = node.children[idx];
              f[i] = Math.min(f[i], node!.cost + dfs(j + 1));
          }
          return f[i];
      };
  
      const ans = dfs(0);
      return ans < inf ? ans : -1;
  }
  
  

All Problems

All Solutions