跳转至

3253. 最小代价构造字符串（简单） 🔒

题目描述

给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs，这两个数组长度相同。

设想一个空字符串 s。

你可以执行以下操作任意次数（包括 零 次）：

  • 选择一个在范围  [0, words.length - 1] 的索引 i。
  • 将 words[i] 追加到 s。
  • 该操作的成本是 costs[i]。

返回使 s 等于 target 的 最小 成本。如果不可能，返回 -1。

 

示例 1：

输入： target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

输出： 7

解释：

  • 选择索引 1 并以成本 1 将 "abc" 追加到 s，得到 s = "abc"。
  • 选择索引 2 并以成本 1 将 "d" 追加到 s，得到 s = "abcd"。
  • 选择索引 4 并以成本 5 将 "ef" 追加到 s，得到 s = "abcdef"。

示例 2：

输入： target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

输出： -1

解释：

无法使 s 等于 target，因此返回 -1。

 

提示：

  • 1 <= target.length <= 2000
  • 1 <= words.length == costs.length <= 50
  • 1 <= words[i].length <= target.length
  • target 和 words[i] 仅由小写英文字母组成。
  • 1 <= costs[i] <= 105

解法

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

我们首先创建一个字典树 $\textit{trie}$，字典树的每个节点包含一个长度为 $26$ 的数组 $\textit{children}$，数组中的每个元素都是一个指向下一个节点的指针。字典树的每个节点还包含一个 $\textit{cost}$ 变量，表示从根节点到当前节点的最小花费。

我们遍历 $\textit{words}$ 数组，将每个单词插入到字典树中，同时更新每个节点的 $\textit{cost}$ 变量。

接下来，我们定义一个记忆化搜索函数 $\textit{dfs}(i)$，表示从 $\textit{target}[i]$ 开始构造字符串的最小花费。那么答案就是 $\textit{dfs}(0)$。

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

  • 如果 $i \geq \textit{len}(\textit{target})$，表示已经构造完整个字符串，返回 $0$。
  • 否则，我们从 $\textit{trie}$ 的根节点开始，遍历 $\textit{target}[i]$ 开始的所有后缀，找到最小花费，即 $\textit{trie}$ 中的 $\textit{cost}$ 变量，加上 $\textit{dfs}(j+1)$ 的结果，其中 $j$ 是 $\textit{target}[i]$ 开始的后缀的结束位置。

最后，如果 $\textit{dfs}(0) < \textit{inf}$，返回 $\textit{dfs}(0)$，否则返回 $-1$。

时间复杂度 $O(n^2 + L)$，空间复杂度 $O(n + L)$。其中 $n$ 是 $\textit{target}$ 的长度，而 $L$ 是 $\textit{words}$ 数组中所有单词的长度之和。

 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
class Trie:
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26
        self.cost = inf

    def insert(self, word: str, cost: int):
        node = self
        for c in word:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.cost = min(node.cost, cost)


class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= len(target):
                return 0
            ans = inf
            node = trie
            for j in range(i, len(target)):
                idx = ord(target[j]) - ord("a")
                if node.children[idx] is None:
                    return ans
                node = node.children[idx]
                ans = min(ans, node.cost + dfs(j + 1))
            return ans

        trie = Trie()
        for word, cost in zip(words, costs):
            trie.insert(word, cost)
        ans = dfs(0)
        return ans if ans < inf else -1

 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
class Trie {
    public final int inf = 1 << 29;
    public Trie[] children = new Trie[26];
    public int cost = inf;

    public void insert(String word, int cost) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.cost = Math.min(node.cost, cost);
    }
}

class Solution {
    private Trie trie = new Trie();
    private char[] target;
    private Integer[] f;

    public int minimumCost(String target, String[] words, int[] costs) {
        for (int i = 0; i < words.length; ++i) {
            trie.insert(words[i], costs[i]);
        }
        this.target = target.toCharArray();
        f = new Integer[target.length()];
        int ans = dfs(0);
        return ans < trie.inf ? ans : -1;
    }

    private int dfs(int i) {
        if (i >= target.length) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        f[i] = trie.inf;
        Trie node = trie;
        for (int j = i; j < target.length; ++j) {
            int idx = target[j] - 'a';
            if (node.children[idx] == null) {
                return f[i];
            }
            node = node.children[idx];
            f[i] = Math.min(f[i], node.cost + dfs(j + 1));
        }
        return f[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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int inf = 1 << 29;

class Trie {
public:
    Trie* children[26]{};
    int cost = inf;

    void insert(string& word, int cost) {
        Trie* node = this;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new Trie();
            }
            node = node->children[idx];
        }
        node->cost = min(node->cost, cost);
    }
};

class Solution {
public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        Trie* trie = new Trie();
        for (int i = 0; i < words.size(); ++i) {
            trie->insert(words[i], costs[i]);
        }
        int n = target.length();
        int f[n];
        memset(f, 0, sizeof(f));
        auto dfs = [&](auto&& dfs, int i) -> int {
            if (i >= n) {
                return 0;
            }
            if (f[i]) {
                return f[i];
            }
            f[i] = inf;
            Trie* node = trie;
            for (int j = i; j < n; ++j) {
                int idx = target[j] - 'a';
                if (!node->children[idx]) {
                    return f[i];
                }
                node = node->children[idx];
                f[i] = min(f[i], node->cost + dfs(dfs, j + 1));
            }
            return f[i];
        };
        int ans = dfs(dfs, 0);
        return ans < inf ? ans : -1;
    }
};

 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
const inf = 1 << 29

type Trie struct {
    children [26]*Trie
    cost     int
}

func NewTrie() *Trie {
    return &Trie{cost: inf}
}

func (t *Trie) insert(word string, cost int) {
    node := t
    for _, c := range word {
        idx := c - 'a'
        if node.children[idx] == nil {
            node.children[idx] = NewTrie()
        }
        node = node.children[idx]
    }
    node.cost = min(node.cost, cost)
}

func minimumCost(target string, words []string, costs []int) int {
    trie := NewTrie()
    for i, word := range words {
        trie.insert(word, costs[i])
    }

    n := len(target)
    f := make([]int, n)
    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
        node := trie
        for j := i; j < n; j++ {
            idx := target[j] - 'a'
            if node.children[idx] == nil {
                return f[i]
            }
            node = node.children[idx]
            f[i] = min(f[i], node.cost+dfs(j+1))
        }
        return f[i]
    }
    if ans := dfs(0); ans < inf {
        return ans
    }
    return -1
}

 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
const inf = 1 << 29;

class Trie {
    children: (Trie | null)[];
    cost: number;

    constructor() {
        this.children = Array(26).fill(null);
        this.cost = inf;
    }

    insert(word: string, cost: number): void {
        let node: Trie = this;
        for (const c of word) {
            const idx = c.charCodeAt(0) - 97;
            if (!node.children[idx]) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx]!;
        }
        node.cost = Math.min(node.cost, cost);
    }
}

function minimumCost(target: string, words: string[], costs: number[]): number {
    const trie = new Trie();
    for (let i = 0; i < words.length; ++i) {
        trie.insert(words[i], costs[i]);
    }

    const n = target.length;
    const f: number[] = Array(n).fill(0);
    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i]) {
            return f[i];
        }
        f[i] = inf;
        let node: Trie | null = trie;
        for (let j = i; j < n; ++j) {
            const idx = target.charCodeAt(j) - 97;
            if (!node?.children[idx]) {
                return f[i];
            }
            node = node.children[idx];
            f[i] = Math.min(f[i], node!.cost + dfs(j + 1));
        }
        return f[i];
    };

    const ans = dfs(0);
    return ans < inf ? ans : -1;
}

评论