Skip to content

3253. Construct String with Minimum Cost (Easy)

  • Time: $O(|\texttt{target}||\textt{words}||\texttt{words[i]}|)$
  • Space: $O(|\texttt{target}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int minimumCost(string target, vector<string>& words, vector<int>& costs) {
    const int n = target.length();
    // dp[i] := the minimum cost to construct target[0..i)
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i)
      for (int j = 0; j < words.size(); ++j)
        if (i >= words[j].length() &&
            target.substr(i - words[j].length(), words[j].length()) ==
                words[j] &&
            dp[i - words[j].length()] != INT_MAX)
          dp[i] = min(dp[i], dp[i - words[j].length()] + costs[j]);

    return dp[n] == INT_MAX ? -1 : dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int minimumCost(String target, String[] words, int[] costs) {
    final int n = target.length();
    // dp[i] := the minimum cost to construct target[0..i)
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int i = 1; i <= n; ++i)
      for (int j = 0; j < words.length; ++j)
        if (i >= words[j].length() && //
            target.substring(i - words[j].length(), i).equals(words[j]) &&
            dp[i - words[j].length()] != Integer.MAX_VALUE)
          dp[i] = Math.min(dp[i], dp[i - words[j].length()] + costs[j]);

    return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def minimumCost(self, target: str, words: list[str], costs: list[int]) -> int:
    n = len(target)
    # dp[i] := the minimum cost to construct target[0:i]
    dp = [0] + [math.inf] * n

    for i in range(1, n + 1):
      for j, (word, cost) in enumerate(zip(words, costs)):
        if (i >= len(word) and
            target[i - len(word):i] == word and
                dp[i - len(word)] != math.inf):
          dp[i] = min(dp[i], dp[i - len(word)] + cost)

    return dp[n] if dp[n] != math.inf else -1