Skip to content

2977. Minimum Cost to Convert String II

  • Time: $O(|\texttt{original}|^3 + |\texttt{source}||\texttt{original}|)$
  • Space: $O(|\texttt{original}|^2 + |\texttt{source}|)$
 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
 public:
  long long minimumCost(string source, string target, vector<string>& original,
                        vector<string>& changed, vector<int>& cost) {
    const unordered_set<int> subLengths = getSubLengths(original);
    const unordered_map<string, int> subToId = getSubToId(original, changed);
    const int subCount = subToId.size();
    // dist[u][v] := the minimum distance to change the substring with id u to
    // the substring with id v
    vector<vector<long>> dist(subCount, vector<long>(subCount, LONG_MAX));
    // dp[i] := the minimum cost to change the first i letters of `source` into
    // `target`, leaving the suffix untouched
    vector<long> dp(source.length() + 1, LONG_MAX);

    for (int i = 0; i < cost.size(); ++i) {
      const int u = subToId.at(original[i]);
      const int v = subToId.at(changed[i]);
      dist[u][v] = min(dist[u][v], static_cast<long>(cost[i]));
    }

    for (int k = 0; k < subCount; ++k)
      for (int i = 0; i < subCount; ++i)
        if (dist[i][k] < LONG_MAX)
          for (int j = 0; j < subCount; ++j)
            if (dist[k][j] < LONG_MAX)
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    dp[0] = 0;

    for (int i = 0; i < source.length(); ++i) {
      if (dp[i] == LONG_MAX)
        continue;
      if (target[i] == source[i])
        dp[i + 1] = min(dp[i + 1], dp[i]);
      for (const int subLength : subLengths) {
        if (i + subLength > source.length())
          continue;
        const string subSource = source.substr(i, subLength);
        const string subTarget = target.substr(i, subLength);
        if (!subToId.contains(subSource) || !subToId.contains(subTarget))
          continue;
        const int u = subToId.at(subSource);
        const int v = subToId.at(subTarget);
        if (dist[u][v] < LONG_MAX)
          dp[i + subLength] = min(dp[i + subLength], dp[i] + dist[u][v]);
      }
    }

    return dp[source.length()] == LONG_MAX ? -1 : dp[source.length()];
  }

 private:
  unordered_map<string, int> getSubToId(const vector<string>& original,
                                        const vector<string>& changed) {
    unordered_map<string, int> subToId;
    for (const string& s : original)
      if (!subToId.contains(s))
        subToId[s] = subToId.size();
    for (const string& s : changed)
      if (!subToId.contains(s))
        subToId[s] = subToId.size();
    return subToId;
  }

  unordered_set<int> getSubLengths(const vector<string>& original) {
    unordered_set<int> subLengths;
    for (const string& s : original)
      subLengths.insert(s.length());
    return subLengths;
  }
};

 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
  public long minimumCost(String source, String target, String[] original, String[] changed,
                          int[] cost) {
    Set<Integer> subLengths = getSubLengths(original);
    Map<String, Integer> subToId = getSubToId(original, changed);
    final int subCount = subToId.size();
    // dist[u][v] := the minimum distance to change the substring with id u to
    // the substring with id v
    long[][] dist = new long[subCount][subCount];
    Arrays.stream(dist).forEach(A -> Arrays.fill(A, Long.MAX_VALUE));
    // dp[i] := the minimum cost to change the first i letters of `source` into
    // `target`, leaving the suffix untouched
    long[] dp = new long[source.length() + 1];
    Arrays.fill(dp, Long.MAX_VALUE);

    for (int i = 0; i < cost.length; ++i) {
      final int u = subToId.get(original[i]);
      final int v = subToId.get(changed[i]);
      dist[u][v] = Math.min(dist[u][v], (long) cost[i]);
    }

    for (int k = 0; k < subCount; ++k)
      for (int i = 0; i < subCount; ++i)
        if (dist[i][k] < Long.MAX_VALUE)
          for (int j = 0; j < subCount; ++j)
            if (dist[k][j] < Long.MAX_VALUE)
              dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

    dp[0] = 0;

    for (int i = 0; i < source.length(); ++i) {
      if (dp[i] == Long.MAX_VALUE)
        continue;
      if (target.charAt(i) == source.charAt(i))
        dp[i + 1] = Math.min(dp[i + 1], dp[i]);
      for (int subLength : subLengths) {
        if (i + subLength > source.length())
          continue;
        String subSource = source.substring(i, i + subLength);
        String subTarget = target.substring(i, i + subLength);
        if (!subToId.containsKey(subSource) || !subToId.containsKey(subTarget))
          continue;
        final int u = subToId.get(subSource);
        final int v = subToId.get(subTarget);
        if (dist[u][v] < Long.MAX_VALUE)
          dp[i + subLength] = Math.min(dp[i + subLength], dp[i] + dist[u][v]);
      }
    }

    return dp[source.length()] == Long.MAX_VALUE ? -1 : dp[source.length()];
  }

  private Map<String, Integer> getSubToId(String[] original, String[] changed) {
    Map<String, Integer> subToId = new HashMap<>();
    for (final String s : original)
      subToId.putIfAbsent(s, subToId.size());
    for (final String s : changed)
      subToId.putIfAbsent(s, subToId.size());
    return subToId;
  }

  private Set<Integer> getSubLengths(String[] original) {
    Set<Integer> subLengths = new HashSet<>();
    for (final String s : original)
      subLengths.add(s.length());
    return subLengths;
  }
}

 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution:
  def minimumCost(
      self,
      source: str,
      target: str,
      original: list[str],
      changed: list[str],
      cost: list[int],
  ) -> int:
    subLengths = set(len(s) for s in original)
    subToId = self._getSubToId(original, changed)
    subCount = len(subToId)
    # dist[u][v] := the minimum distance to change the substring with id u to
    # the substring with id v
    dist = [[math.inf for _ in range(subCount)] for _ in range(subCount)]
    # dp[i] := the minimum cost to change the first i letters of `source` into
    # `target`, leaving the suffix untouched
    dp = [math.inf for _ in range(len(source) + 1)]

    for a, b, c in zip(original, changed, cost):
      u = subToId[a]
      v = subToId[b]
      dist[u][v] = min(dist[u][v], c)

    for k in range(subCount):
      for i in range(subCount):
        if dist[i][k] < math.inf:
          for j in range(subCount):
            if dist[k][j] < math.inf:
              dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    dp[0] = 0

    for i, (s, t) in enumerate(zip(source, target)):
      if dp[i] == math.inf:
        continue
      if s == t:
        dp[i + 1] = min(dp[i + 1], dp[i])
      for subLength in subLengths:
        if i + subLength > len(source):
          continue
        subSource = source[i:i + subLength]
        subTarget = target[i:i + subLength]
        if subSource not in subToId or subTarget not in subToId:
          continue
        u = subToId[subSource]
        v = subToId[subTarget]
        if dist[u][v] != math.inf:
          dp[i + subLength] = min(dp[i + subLength], dp[i] + dist[u][v])

    return -1 if dp[len(source)] == math.inf else dp[len(source)]

  def _getSubToId(self, original: str, changed: str) -> dict[str, int]:
    subToId = {}
    for s in original + changed:
      if s not in subToId:
        subToId[s] = len(subToId)
    return subToId