跳转至

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

来源第 377 场周赛 Q4难度困难分数2695

题目描述

给你两个下标从 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 算法 + 记忆化搜索

思考

改写对象变成整段子串,且 \(\textit{source}\)、 \(\textit{target}\) 须同步替换。候选串不超过 \(100\),先用字典树编号,再在编号点上 Floyd 得到任意替换代价。剩余问题是按位置切分:能匹配一对原串/目标串则付 \(g[p][q]\),或单字符相等则免费前进。

\(\textit{dfs}(i)\) 记忆化从 \(i\) 切到末尾的最小代价,两指针同步走字典树。串长 \(1000\),状态线性,转移与匹配长度同阶。

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

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

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

函数 \(\textit{dfs}(i)\) 的计算过程如下:

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

综上,我们可以得到:

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

其中 \(x\) 和 \(y\) 分别是 \(\textit{source}[i..j]\) 和 \(\textit{target}[i..j]\) 在字典树中对应的整数编号。

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

时间复杂度 \(O(m^3 + n^2 + mn)\),空间复杂度 \(O(m^2 + mn + n)\)。其中 \(m\) 和 \(n\) 分别是数组 \(\textit{original}\) 和 \(\textit{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
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
 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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;
    }
}
 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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;
    }
};
 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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)
}
 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
72
73
74
75
76
77
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;
}
  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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
use std::cmp::min;

struct Node {
    children: [Option<Box<Node>>; 26],
    v: i32,
}

impl Node {
    fn new() -> Self {
        Self {
            children: std::array::from_fn(|_| None),
            v: -1,
        }
    }
}

impl Solution {
    pub fn minimum_cost(
        source: String,
        target: String,
        original: Vec<String>,
        changed: Vec<String>,
        cost: Vec<i32>,
    ) -> i64 {
        let inf: i64 = 1 << 60;
        let mut root = Box::new(Node::new());
        let mut idx: usize = 0;
        let m = cost.len();
        let n = m << 1;

        let mut g = vec![vec![inf; n]; n];
        for i in 0..n {
            g[i][i] = 0;
        }

        let mut insert = |w: &str, root: &mut Box<Node>, idx: &mut usize| -> usize {
            let mut node: &mut Box<Node> = root;
            for c in w.bytes() {
                let i = (c - b'a') as usize;
                if node.children[i].is_none() {
                    node.children[i] = Some(Box::new(Node::new()));
                }
                node = node.children[i].as_mut().unwrap();
            }
            if node.v < 0 {
                node.v = *idx as i32;
                *idx += 1;
            }
            node.v as usize
        };

        for i in 0..m {
            let x = insert(&original[i], &mut root, &mut idx);
            let y = insert(&changed[i], &mut root, &mut idx);
            g[x][y] = min(g[x][y], cost[i] as i64);
        }

        for k in 0..idx {
            for i in 0..idx {
                if g[i][k] >= inf {
                    continue;
                }
                for j in 0..idx {
                    let v = g[i][k] + g[k][j];
                    if v < g[i][j] {
                        g[i][j] = v;
                    }
                }
            }
        }

        let s = source.into_bytes();
        let t = target.into_bytes();
        let len = s.len();
        let mut f: Vec<Option<i64>> = vec![None; len];

        fn dfs(
            i: usize,
            s: &[u8],
            t: &[u8],
            root: &Box<Node>,
            g: &Vec<Vec<i64>>,
            f: &mut Vec<Option<i64>>,
            inf: i64,
        ) -> i64 {
            if i >= s.len() {
                return 0;
            }
            if let Some(v) = f[i] {
                return v;
            }
            let mut res = if s[i] == t[i] {
                dfs(i + 1, s, t, root, g, f, inf)
            } else {
                inf
            };
            let mut p: Option<&Box<Node>> = Some(root);
            let mut q: Option<&Box<Node>> = Some(root);
            for j in i..s.len() {
                p = p.and_then(|x| x.children[(s[j] - b'a') as usize].as_ref());
                q = q.and_then(|x| x.children[(t[j] - b'a') as usize].as_ref());
                if p.is_none() || q.is_none() {
                    break;
                }
                let pv = p.unwrap().v;
                let qv = q.unwrap().v;
                if pv < 0 || qv < 0 {
                    continue;
                }
                let c = g[pv as usize][qv as usize];
                if c < inf {
                    let v = c + dfs(j + 1, s, t, root, g, f, inf);
                    if v < res {
                        res = v;
                    }
                }
            }
            f[i] = Some(res);
            res
        }

        let ans = dfs(0, &s, &t, &root, &g, &mut f, inf);
        if ans >= inf {
            -1
        } else {
            ans
        }
    }
}

方法二:字典树 + Floyd 算法 + 动态规划

思考

把 \(\textit{source}\) 整段换成 \(\textit{target}\) 的每一种切法是指数级的。串长可以到 \(1000\),而当前字符相等时第一次递归总是落到下一位置,调用深度就是 \(n\)。从下标 \(i\) 起的最小代价只依赖更靠后的后缀。候选串不超过 \(100\),先用字典树编号,Floyd 得到任意一对的替换代价。令 \(f[n]=0\),按 \(i\) 从 \(n-1\) 降到 \(0\):字符相等则可以免费用 \(f[i+1]\),同时沿字典树同步走,每对已经编号的子串再用 \(f[j+1]+g[x][y]\) 更新。 \(f[0]\) 仍不小于哨兵时返回 \(-1\)。

我们把 original 和 changed 中的每个字符串看作一个节点,用字典树为它们编号。 \(g[x][y]\) 表示编号 \(x\) 的字符串换成编号 \(y\) 的最小代价,初值为 \(\infty\),自身为 \(0\)。用 Floyd 算法求出任意两个编号之间的最小代价。

令 \(f[i]\) 表示把 \(\textit{source}[i..]\) 变成 \(\textit{target}[i..]\) 的最小代价, \(f[n] = 0\)。按 \(i\) 从 \(n - 1\) 降到 \(0\)。若 \(\textit{source}[i] = \textit{target}[i]\),可以免费留下这一位,先取 \(f[i + 1]\)。再从 \(i\) 起沿字典树同步匹配 \(\textit{source}\) 与 \(\textit{target}\),一旦前缀 \(\textit{source}[i..j]\) 和 \(\textit{target}[i..j]\) 都有编号 \(x\)、 \(y\),就用 \(f[j + 1] + g[x][y]\) 更新 \(f[i]\)。

答案为 \(f[0]\)。若它不小于预先设定的上界,返回 \(-1\)。

时间复杂度 \(O(m^3 + n^2 + mn)\),空间复杂度 \(O(m^2 + mn + n)\)。其中 \(m\) 和 \(n\) 分别是数组 \(\textit{original}\) 和 \(\textit{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
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

        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):
                    if g[i][k] + g[k][j] < g[i][j]:
                        g[i][j] = g[i][k] + g[k][j]

        n = len(source)
        f = [inf] * (n + 1)
        f[n] = 0
        for i in range(n - 1, -1, -1):
            res = f[i + 1] if source[i] == target[i] else inf
            p = q = root
            for j in range(i, n):
                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, f[j + 1] + g[p.v][q.v])
            f[i] = res
        return -1 if f[0] >= inf else f[0]
 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
72
73
74
75
76
77
78
79
80
81
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;

    public long minimumCost(
        String source, String target, String[] original, String[] changed, int[] cost) {
        int m = cost.length;
        g = new long[m << 1][m << 1];
        char[] s = source.toCharArray();
        char[] 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]);
                }
            }
        }
        int n = s.length;
        long[] f = new long[n + 1];
        for (int i = 0; i < n; ++i) {
            f[i] = inf;
        }
        for (int i = n - 1; i >= 0; --i) {
            long res = s[i] == t[i] ? f[i + 1] : inf;
            Node p = root, q = root;
            for (int j = i; j < n; ++j) {
                int a = s[j] - 'a';
                int b = t[j] - 'a';
                if (p.children[a] == null || q.children[b] == null) {
                    break;
                }
                p = p.children[a];
                q = q.children[b];
                if (p.v < 0 || q.v < 0) {
                    continue;
                }
                long w = g[p.v][q.v];
                if (w < inf) {
                    res = Math.min(res, w + f[j + 1]);
                }
            }
            f[i] = res;
        }
        return f[0] >= inf ? -1 : f[0];
    }

    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;
    }
}
 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
72
73
74
75
76
77
78
79
80
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 = 0;

    vector<vector<long long>> g;

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

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));
        for (int i = 0; i < (int) 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]);
                }
            }
        }
        int n = source.size();
        vector<long long> f(n + 1, inf);
        f[n] = 0;
        for (int i = n - 1; i >= 0; --i) {
            long long res = source[i] == target[i] ? f[i + 1] : inf;
            Node* p = root;
            Node* q = root;
            for (int j = i; j < n; ++j) {
                p = p->children[source[j] - 'a'];
                q = q->children[target[j] - 'a'];
                if (p == nullptr || q == nullptr) {
                    break;
                }
                if (p->v < 0 || q->v < 0) {
                    continue;
                }
                long long w = g[p->v][q->v];
                if (w < inf) {
                    res = min(res, w + f[j + 1]);
                }
            }
            f[i] = res;
        }
        return f[0] >= inf ? -1 : f[0];
    }
};
 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
72
73
74
75
76
77
78
79
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+1)
    for i := 0; i < n; i++ {
        f[i] = inf
    }
    for i := n - 1; i >= 0; i-- {
        if source[i] == target[i] {
            f[i] = f[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], f[j+1]+g[p.v][q.v])
        }
    }
    if f[0] >= inf {
        return -1
    }
    return int64(f[0])
}
 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
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 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;
    };
    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 f: number[] = Array(n + 1).fill(Infinity);
    f[n] = 0;
    for (let i = n - 1; i >= 0; --i) {
        let res: number = source[i] === target[i] ? f[i + 1] : Infinity;
        let p: Node | null = root;
        let q: Node | null = root;
        for (let j = i; j < n; ++j) {
            p = p.children[source.charCodeAt(j) - 97];
            q = q.children[target.charCodeAt(j) - 97];
            if (p === null || q === null) {
                break;
            }
            if (p.v < 0 || q.v < 0) {
                continue;
            }
            res = Math.min(res, g[p.v][q.v] + f[j + 1]);
        }
        f[i] = res;
    }
    return f[0] >= Infinity ? -1 : f[0];
}
  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
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
use std::cmp::min;

struct Node {
    children: [Option<Box<Node>>; 26],
    v: i32,
}

impl Node {
    fn new() -> Self {
        Self {
            children: std::array::from_fn(|_| None),
            v: -1,
        }
    }
}

impl Solution {
    pub fn minimum_cost(
        source: String,
        target: String,
        original: Vec<String>,
        changed: Vec<String>,
        cost: Vec<i32>,
    ) -> i64 {
        let inf: i64 = 1 << 60;
        let mut root = Box::new(Node::new());
        let mut idx: usize = 0;
        let m = cost.len();
        let n = m << 1;

        let mut g = vec![vec![inf; n]; n];
        for i in 0..n {
            g[i][i] = 0;
        }

        let mut insert = |w: &str, root: &mut Box<Node>, idx: &mut usize| -> usize {
            let mut node: &mut Box<Node> = root;
            for c in w.bytes() {
                let i = (c - b'a') as usize;
                if node.children[i].is_none() {
                    node.children[i] = Some(Box::new(Node::new()));
                }
                node = node.children[i].as_mut().unwrap();
            }
            if node.v < 0 {
                node.v = *idx as i32;
                *idx += 1;
            }
            node.v as usize
        };

        for i in 0..m {
            let x = insert(&original[i], &mut root, &mut idx);
            let y = insert(&changed[i], &mut root, &mut idx);
            g[x][y] = min(g[x][y], cost[i] as i64);
        }

        for k in 0..idx {
            for i in 0..idx {
                if g[i][k] >= inf {
                    continue;
                }
                for j in 0..idx {
                    let v = g[i][k] + g[k][j];
                    if v < g[i][j] {
                        g[i][j] = v;
                    }
                }
            }
        }

        let s = source.into_bytes();
        let t = target.into_bytes();
        let len = s.len();
        let mut f = vec![inf; len + 1];
        f[len] = 0;
        for i in (0..len).rev() {
            let mut res = if s[i] == t[i] { f[i + 1] } else { inf };
            let mut p: Option<&Box<Node>> = Some(&root);
            let mut q: Option<&Box<Node>> = Some(&root);
            for j in i..len {
                p = p.and_then(|x| x.children[(s[j] - b'a') as usize].as_ref());
                q = q.and_then(|x| x.children[(t[j] - b'a') as usize].as_ref());
                if p.is_none() || q.is_none() {
                    break;
                }
                let pv = p.unwrap().v;
                let qv = q.unwrap().v;
                if pv < 0 || qv < 0 {
                    continue;
                }
                let c = g[pv as usize][qv as usize];
                if c < inf {
                    let v = c + f[j + 1];
                    if v < res {
                        res = v;
                    }
                }
            }
            f[i] = res;
        }
        if f[0] >= inf {
            -1
        } else {
            f[0]
        }
    }
}

评论