Question

2977. 转换字符串的最小成本 II

English Version

题目描述

给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由 小写 英文字母组成。

另给你两个下标从 0 开始的字符串数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符串 original[i] 更改为字符串 changed[i] 的成本。

你从字符串 source 开始。在一次操作中，如果 存在 任意 下标 j 满足 cost[j] == z  、original[j] == x 以及 changed[j] == y ，你就可以选择字符串中的 子串 x 并以 z 的成本将其更改为 y 。 你可以执行 任意数量 的操作，但是任两次操作必须满足 以下两个 条件 之一 ：

• 在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 b < c  或 d < a 。换句话说，两次操作中选择的下标 不相交 。
• 在两次操作中选择的子串分别是 source[a..b] 和 source[c..d] ，满足 a == c 且 b == d 。换句话说，两次操作中选择的下标 相同 。

返回将字符串 source 转换为字符串 target 所需的 最小 成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

 

示例 1：

输入：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]
输出：28
解释：将 "abcd" 转换为 "acbe"，执行以下操作：
- 将子串 source[1..1] 从 "b" 改为 "c" ，成本为 5 。
- 将子串 source[2..2] 从 "c" 改为 "e" ，成本为 1 。
- 将子串 source[2..2] 从 "e" 改为 "b" ，成本为 2 。
- 将子串 source[3..3] 从 "d" 改为 "e" ，成本为 20 。
产生的总成本是 5 + 1 + 2 + 20 = 28 。 
可以证明这是可能的最小成本。

示例 2：

输入：source = "abcdefgh", target = "acdeeghh", original = ["bcd","fgh","thh"], changed = ["cde","thh","ghh"], cost = [1,3,5]
输出：9
解释：将 "abcdefgh" 转换为 "acdeeghh"，执行以下操作：
- 将子串 source[1..3] 从 "bcd" 改为 "cde" ，成本为 1 。
- 将子串 source[5..7] 从 "fgh" 改为 "thh" ，成本为 3 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交。
- 将子串 source[5..7] 从 "thh" 改为 "ghh" ，成本为 5 。可以执行此操作，因为下标 [5,7] 与第一次操作选中的下标不相交，且与第二次操作选中的下标相同。
产生的总成本是 1 + 3 + 5 = 9 。
可以证明这是可能的最小成本。

示例 3：

输入：source = "abcdefgh", target = "addddddd", original = ["bcd","defgh"], changed = ["ddd","ddddd"], cost = [100,1578]
输出：-1
解释：无法将 "abcdefgh" 转换为 "addddddd" 。
如果选择子串 source[1..3] 执行第一次操作，以将 "abcdefgh" 改为 "adddefgh" ，你无法选择子串 source[3..7] 执行第二次操作，因为两次操作有一个共用下标 3 。
如果选择子串 source[3..7] 执行第一次操作，以将 "abcdefgh" 改为 "abcddddd" ，你无法选择子串 source[1..3] 执行第二次操作，因为两次操作有一个共用下标 3 。

 

提示：

• 1 <= source.length == target.length <= 1000
• source、target 均由小写英文字母组成
• 1 <= cost.length == original.length == changed.length <= 100
• 1 <= original[i].length == changed[i].length <= source.length
• original[i]、changed[i] 均由小写英文字母组成
• original[i] != changed[i]
• 1 <= cost[i] <= 106

解法

方法一：字典树 + Floyd 算法 + 记忆化搜索

根据题目描述，我们可以将每个字符串看作一个节点，每对字符串的转换成本看作一条有向边。那么我们先初始化一个 $26 \times 26$ 的二维数组 $g$，其中 $g[i][j]$ 表示字符串 $i$ 转换成字符串 $j$ 的最小成本。初始时 $g[i][j] = \infty$，如果 $i = j$，那么 $g[i][j] = 0$。在这里，我们可以借助字典树存储 original 和 changed 中的字符串以及对应的整数编号。

然后，我们使用 Floyd 算法计算出任意两个字符串之间的最小成本。

接下来，我们定义函数 $dfs(i)$ 表示将字符串 $source[i..]$ 转换为字符串 $target[i..]$ 所需的最小成本。那么答案就是 $dfs(0)$。

函数 $dfs(i)$ 的计算过程如下：

• 如果 $i \geq |source|$，说明不需要转换，返回 $0$。
• 否则，如果 $source[i] = target[i]$，那么可以直接跳过，我们直接递归计算 $dfs(i + 1)$。我们也可以在 $[i, |source|)$ 的范围内枚举下标 $j$，如果 $source[i..j]$ 和 $target[i..j]$ 都在字典树中，且其对应的整数编号 $x$ 和 $y$ 都大于等于 $0$，那么我们可以将 $dfs(j + 1)$ 和 $g[x][y]$ 相加，得到一种转换方案的成本，我们取所有方案中的最小值。

综上，我们可以得到：

$$ 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} $$

其中 $x$ 和 $y$ 分别是 $source[i..j]$ 和 $target[i..j]$ 在字典树中对应的整数编号。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(m^3 + n^2 + m \times n)$，空间复杂度 $O(m^2 + m \times n + n)$。其中 $m$ 和 $n$ 分别是数组 $original$ 和 $source$ 的长度。

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;
}