Skip to content

3213. Construct String with Minimum Cost 👍

  • Time: $O(n^2)$
  • Space: $O(\Sigma |\texttt{words[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int minimumCost(string target, vector<string>& words, vector<int>& costs) {
    constexpr int kMax = 1'000'000'000;
    const int n = target.length();
    // dp[i] := the minimum cost to construct target[0..i)
    vector<int> dp(n + 1, kMax);
    dp[0] = 0;
    // minCost[c][word] := the minimum cost to construct word starting with `c`
    vector<unordered_map<string, int>> minCost(26);

    for (int i = 0; i < words.size(); ++i) {
      const int index = words[i][0] - 'a';
      const string& word = words[i];
      minCost[index][word] =
          min(minCost[index].contains(word) ? minCost[index][word] : kMax,
              costs[i]);
    }

    for (int i = 0; i < n; ++i)
      for (const auto& [word, cost] : minCost[target[i] - 'a']) {
        const int j = i + word.length();
        if (j <= n && cost + dp[i] < dp[j] &&
            string_view(target.data() + i, word.length()) == word)
          dp[j] = cost + dp[i];
      }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public int minimumCost(String target, String[] words, int[] costs) {
    final int kMax = 1_000_000_000;
    final int n = target.length();
    // dp[i] := the minimum cost to construct target[0..i)
    int[] dp = new int[n + 1];
    Arrays.fill(dp, kMax);
    dp[0] = 0;
    // minCost[c][word] := the minimum cost to construct word starting with `c`
    Map<String, Integer>[] minCost = new HashMap[26];

    for (int i = 0; i < 26; ++i)
      minCost[i] = new HashMap<>();

    for (int i = 0; i < words.length; ++i) {
      final int index = words[i].charAt(0) - 'a';
      final String word = words[i];
      minCost[index].put(word, Math.min(minCost[index].getOrDefault(word, kMax), costs[i]));
    }

    for (int i = 0; i < n; ++i)
      for (Map.Entry<String, Integer> entry : minCost[target.charAt(i) - 'a'].entrySet()) {
        final String word = entry.getKey();
        final int cost = entry.getValue();
        final int j = i + word.length();
        if (j <= n && cost + dp[i] < dp[j] && isMatch(target, i, word))
          dp[j] = cost + dp[i];
      }

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

  private boolean isMatch(final String target, int start, final String word) {
    for (int i = 0; i < word.length(); ++i)
      if (target.charAt(start + i) != word.charAt(i))
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
    # minCost[c][word] := the minimum cost to construct word starting with `c`
    minCost: dict[str, dict[str, int]] = collections.defaultdict(dict)

    for word, cost in zip(words, costs):
      c = word[0]
      minCost[c][word] = min(minCost[c].get(word, math.inf), cost)

    for i, c in enumerate(target):
      for word, cost in minCost[c].items():
        j = i + len(word)
        if j <= n and cost + dp[i] < dp[j] and target[i:j] == word:
          dp[j] = cost + dp[i]

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