Question

2977. Minimum Cost to Convert String II

中文文档

Description

You are given two 0-indexed strings source and target, both of length n and consisting of lowercase English characters. You are also given two 0-indexed string arrays original and changed, and an integer array cost, where cost[i] represents the cost of converting the string original[i] to the string changed[i].

You start with the string source. In one operation, you can pick a substring x from the string, and change it to y at a cost of z if there exists any index j such that cost[j] == z, original[j] == x, and changed[j] == y. You are allowed to do any number of operations, but any pair of operations must satisfy either of these two conditions:

• The substrings picked in the operations are source[a..b] and source[c..d] with either b < c or d < a. In other words, the indices picked in both operations are disjoint.
• The substrings picked in the operations are source[a..b] and source[c..d] with a == c and b == d. In other words, the indices picked in both operations are identical.

Return _the minimum cost to convert the string _source_ to the string _target_ using any number of operations_. _If it is impossible to convert_ source _to_ target,_ return_ -1.

Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].

 

Example 1:

Input: source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20]
Output: 28
Explanation: To convert "abcd" to "acbe", do the following operations:
- Change substring source[1..1] from "b" to "c" at a cost of 5.
- Change substring source[2..2] from "c" to "e" at a cost of 1.
- Change substring source[2..2] from "e" to "b" at a cost of 2.
- Change substring source[3..3] from "d" to "e" at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28. 
It can be shown that this is the minimum possible cost.

Example 2:

Input: source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
Output: 9
Explanation: To convert "abcdefgh" to "acdeeghh", do the following operations:
- Change substring source[1..3] from "bcd" to "cde" at a cost of 1.
- Change substring source[5..7] from "fgh" to "thh" at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
- Change substring source[5..7] from "thh" to "ghh" at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.

Example 3:

Input: source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
Output: -1
Explanation: It is impossible to convert "abcdefgh" to "addddddd".
If you select substring source[1..3] as the first operation to change "abcdefgh" to "adddefgh", you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change "abcdefgh" to "abcddddd", you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.

 

Constraints:

• 1 <= source.length == target.length <= 1000
• source, target consist only of lowercase English characters.
• 1 <= cost.length == original.length == changed.length <= 100
• 1 <= original[i].length == changed[i].length <= source.length
• original[i], changed[i] consist only of lowercase English characters.
• original[i] != changed[i]
• 1 <= cost[i] <= 106

Solutions

Solution 1: Trie + Floyd Algorithm + Memoization Search

According to the problem description, we can consider each string as a node, and the conversion cost between each pair of strings as a directed edge. We first initialize a $26 \times 26$ two-dimensional array $g$, where $g[i][j]$ represents the minimum cost of converting string $i$ to string $j$. Initially, $g[i][j] = \infty$, and if $i = j$, then $g[i][j] = 0$. Here, we can use a trie to store the strings in original and changed along with their corresponding integer identifiers.

Next, we use the Floyd algorithm to calculate the minimum cost between any two strings.

Then, we define a function $dfs(i)$ to represent the minimum cost of converting the string $source[i..]$ to the string $target[i..]$. The answer is $dfs(0)$.

The calculation process of the function $dfs(i)$ is as follows:

• If $i \geq |source|$, no conversion is needed, return $0$.
• Otherwise, if $source[i] = target[i]$, we can skip directly and recursively calculate $dfs(i + 1)$. We can also enumerate the index $j$ in the range $[i, |source|)$, if $source[i..j]$ and $target[i..j]$ are both in the trie, and their corresponding integer identifiers $x$ and $y$ are both greater than or equal to $0$, then we can add $dfs(j + 1)$ and $g[x][y]$ to get the cost of one conversion scheme, and we take the minimum value among all schemes.

In summary, we can get:

$$ dfs(i) = \begin{cases} 0, & i \geq |source| \ dfs(i + 1), & source[i] = target[i] \ \min_{i \leq j < |source|} { dfs(j + 1) + g[x][y] }, & \text{otherwise} \end{cases} $$

Where $x$ and $y$ are the integer identifiers of $source[i..j]$ and $target[i..j]$ in the trie, respectively.

To avoid repeated calculations, we can use memoization search.

The time complexity is $O(m^3 + n^2 + m \times n)$, and the space complexity is $O(m^2 + m \times n + n)$. Where $m$ and $n$ are the lengths of the arrays original and source, respectively.

class Node:
  __slots__ = ["children", "v"]

  def __init__(self):
    self.children: List[Node | None] = [None] * 26
    self.v = -1


class Solution:
  def minimumCost(
    self,
    source: str,
    target: str,
    original: List[str],
    changed: List[str],
    cost: List[int],
  ) -> int:
    m = len(cost)
    g = [[inf] * (m << 1) for _ in range(m << 1)]
    for i in range(m << 1):
      g[i][i] = 0
    root = Node()
    idx = 0

    def insert(w: str) -> int:
      node = root
      for c in w:
        i = ord(c) - ord("a")
        if node.children[i] is None:
          node.children[i] = Node()
        node = node.children[i]
      if node.v < 0:
        nonlocal idx
        node.v = idx
        idx += 1
      return node.v

    @cache
    def dfs(i: int) -> int:
      if i >= len(source):
        return 0
      res = dfs(i + 1) if source[i] == target[i] else inf
      p = q = root
      for j in range(i, len(source)):
        p = p.children[ord(source[j]) - ord("a")]
        q = q.children[ord(target[j]) - ord("a")]
        if p is None or q is None:
          break
        if p.v < 0 or q.v < 0:
          continue
        res = min(res, dfs(j + 1) + g[p.v][q.v])
      return res

    for x, y, z in zip(original, changed, cost):
      x = insert(x)
      y = insert(y)
      g[x][y] = min(g[x][y], z)
    for k in range(idx):
      for i in range(idx):
        if g[i][k] >= inf:
          continue
        for j in range(idx):
          # g[i][j] = min(g[i][j], g[i][k] + g[k][j])
          if g[i][k] + g[k][j] < g[i][j]:
            g[i][j] = g[i][k] + g[k][j]

    ans = dfs(0)
    return -1 if ans >= inf else ans

class Node {
  Node[] children = new Node[26];
  int v = -1;
}

class Solution {
  private final long inf = 1L << 60;
  private Node root = new Node();
  private int idx;

  private long[][] g;
  private char[] s;
  private char[] t;
  private Long[] f;

  public long minimumCost(
    String source, String target, String[] original, String[] changed, int[] cost) {
    int m = cost.length;
    g = new long[m << 1][m << 1];
    s = source.toCharArray();
    t = target.toCharArray();
    for (int i = 0; i < g.length; ++i) {
      Arrays.fill(g[i], inf);
      g[i][i] = 0;
    }
    for (int i = 0; i < m; ++i) {
      int x = insert(original[i]);
      int y = insert(changed[i]);
      g[x][y] = Math.min(g[x][y], cost[i]);
    }
    for (int k = 0; k < idx; ++k) {
      for (int i = 0; i < idx; ++i) {
        if (g[i][k] >= inf) {
          continue;
        }
        for (int j = 0; j < idx; ++j) {
          g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }
    f = new Long[s.length];
    long ans = dfs(0);
    return ans >= inf ? -1 : ans;
  }

  private int insert(String w) {
    Node node = root;
    for (char c : w.toCharArray()) {
      int i = c - 'a';
      if (node.children[i] == null) {
        node.children[i] = new Node();
      }
      node = node.children[i];
    }
    if (node.v < 0) {
      node.v = idx++;
    }
    return node.v;
  }

  private long dfs(int i) {
    if (i >= s.length) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    long res = s[i] == t[i] ? dfs(i + 1) : inf;
    Node p = root, q = root;
    for (int j = i; j < s.length; ++j) {
      p = p.children[s[j] - 'a'];
      q = q.children[t[j] - 'a'];
      if (p == null || q == null) {
        break;
      }
      if (p.v < 0 || q.v < 0) {
        continue;
      }
      long t = g[p.v][q.v];
      if (t < inf) {
        res = Math.min(res, t + dfs(j + 1));
      }
    }
    return f[i] = res;
  }
}

class Node {
public:
  Node* children[26];
  int v = -1;
  Node() {
    fill(children, children + 26, nullptr);
  }
};

class Solution {
private:
  const long long inf = 1LL << 60;
  Node* root = new Node();
  int idx;

  vector<vector<long long>> g;
  string s;
  string t;
  vector<long long> f;

public:
  long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
    int m = cost.size();
    g = vector<vector<long long>>(m << 1, vector<long long>(m << 1, inf));
    s = source;
    t = target;

    for (int i = 0; i < g.size(); ++i) {
      g[i][i] = 0;
    }

    for (int i = 0; i < m; ++i) {
      int x = insert(original[i]);
      int y = insert(changed[i]);
      g[x][y] = min(g[x][y], static_cast<long long>(cost[i]));
    }

    for (int k = 0; k < idx; ++k) {
      for (int i = 0; i < idx; ++i) {
        if (g[i][k] >= inf) {
          continue;
        }
        for (int j = 0; j < idx; ++j) {
          g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }

    f = vector<long long>(s.length(), -1);
    long long ans = dfs(0);
    return ans >= inf ? -1 : ans;
  }

private:
  int insert(const string& w) {
    Node* node = root;
    for (char c : w) {
      int i = c - 'a';
      if (node->children[i] == nullptr) {
        node->children[i] = new Node();
      }
      node = node->children[i];
    }
    if (node->v < 0) {
      node->v = idx++;
    }
    return node->v;
  }

  long long dfs(int i) {
    if (i >= s.length()) {
      return 0;
    }
    if (f[i] != -1) {
      return f[i];
    }
    long long res = (s[i] == t[i]) ? dfs(i + 1) : inf;
    Node* p = root;
    Node* q = root;
    for (int j = i; j < s.length(); ++j) {
      p = p->children[s[j] - 'a'];
      q = q->children[t[j] - 'a'];
      if (p == nullptr || q == nullptr) {
        break;
      }
      if (p->v < 0 || q->v < 0) {
        continue;
      }
      long long temp = g[p->v][q->v];
      if (temp < inf) {
        res = min(res, temp + dfs(j + 1));
      }
    }
    return f[i] = res;
  }
};

type Node struct {
  children [26]*Node
  v    int
}

func newNode() *Node {
  return &Node{v: -1}
}

func minimumCost(source string, target string, original []string, changed []string, cost []int) int64 {
  inf := 1 << 60
  root := newNode()
  idx := 0
  m := len(cost)
  g := make([][]int, m<<1)
  for i := range g {
    g[i] = make([]int, m<<1)
    for j := range g[i] {
      g[i][j] = inf
    }
    g[i][i] = 0
  }
  insert := func(w string) int {
    node := root
    for _, c := range w {
      i := c - 'a'
      if node.children[i] == nil {
        node.children[i] = newNode()
      }
      node = node.children[i]
    }
    if node.v < 0 {
      node.v = idx
      idx++
    }
    return node.v
  }
  for i := range original {
    x := insert(original[i])
    y := insert(changed[i])
    g[x][y] = min(g[x][y], cost[i])
  }
  for k := 0; k < idx; k++ {
    for i := 0; i < idx; i++ {
      if g[i][k] >= inf {
        continue
      }
      for j := 0; j < idx; j++ {
        g[i][j] = min(g[i][j], g[i][k]+g[k][j])
      }
    }
  }
  n := len(source)
  f := make([]int, n)
  for i := range f {
    f[i] = -1
  }
  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
    if source[i] == target[i] {
      f[i] = dfs(i + 1)
    }
    p, q := root, root
    for j := i; j < n; j++ {
      p = p.children[source[j]-'a']
      q = q.children[target[j]-'a']
      if p == nil || q == nil {
        break
      }
      if p.v < 0 || q.v < 0 {
        continue
      }
      f[i] = min(f[i], dfs(j+1)+g[p.v][q.v])
    }
    return f[i]
  }
  ans := dfs(0)
  if ans >= inf {
    ans = -1
  }
  return int64(ans)
}

class Node {
  children: (Node | null)[] = Array(26).fill(null);
  v: number = -1;
}

function minimumCost(
  source: string,
  target: string,
  original: string[],
  changed: string[],
  cost: number[],
): number {
  const m = cost.length;
  const n = source.length;
  const g: number[][] = Array.from({ length: m << 1 }, () => Array(m << 1).fill(Infinity));
  const root: Node = new Node();
  let idx: number = 0;
  const f: number[] = Array(n).fill(-1);
  const insert = (w: string): number => {
    let node: Node = root;
    for (const c of w) {
      const i: number = c.charCodeAt(0) - 'a'.charCodeAt(0);
      if (node.children[i] === null) {
        node.children[i] = new Node();
      }
      node = node.children[i] as Node;
    }
    if (node.v < 0) {
      node.v = idx++;
    }
    return node.v;
  };

  const dfs = (i: number): number => {
    if (i >= n) {
      return 0;
    }
    if (f[i] !== -1) {
      return f[i];
    }
    let res: number = source[i] === target[i] ? dfs(i + 1) : Infinity;
    let p: Node = root;
    let q: Node = root;
    for (let j = i; j < source.length; ++j) {
      p = p.children[source[j].charCodeAt(0) - 'a'.charCodeAt(0)] as Node;
      q = q.children[target[j].charCodeAt(0) - 'a'.charCodeAt(0)] as Node;
      if (p === null || q === null) {
        break;
      }
      if (p.v < 0 || q.v < 0) {
        continue;
      }
      const t: number = g[p.v][q.v];
      res = Math.min(res, t + dfs(j + 1));
    }
    return (f[i] = res);
  };

  for (let i = 0; i < m; ++i) {
    const x: number = insert(original[i]);
    const y: number = insert(changed[i]);
    g[x][y] = Math.min(g[x][y], cost[i]);
  }

  for (let k = 0; k < idx; ++k) {
    for (let i = 0; i < idx; ++i) {
      if (g[i][k] >= Infinity) {
        continue;
      }
      for (let j = 0; j < idx; ++j) {
        g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
  const ans: number = dfs(0);
  return ans >= Infinity ? -1 : ans;
}