跳转至

3213. 最小代价构造字符串

题目描述

给你一个字符串 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 <= 5 * 104
  • 1 <= words.length == costs.length <= 5 * 104
  • 1 <= words[i].length <= target.length
  • 所有 words[i].length 的总和小于或等于 5 * 104
  • target 和 words[i] 仅由小写英文字母组成。
  • 1 <= costs[i] <= 104

解法

方法一：字符串哈希 + 动态规划 + 枚举长度

我们定义 \(f[i]\) 表示构造 \(\textit{target}\) 前 \(i\) 个字符的最小代价，初始时 \(f[0] = 0\)，其余值均为无穷大。答案为 \(f[n]\)，其中 \(n\) 是 \(\textit{target}\) 的长度。

对于当前 \(f[i]\)，考虑枚举单词的长度 \(j\)，如果 \(j \leq i\)，那么我们可以考虑从 \(i - j + 1\) 到 \(i\) 这段区间的哈希值，如果这个哈希值对应的单词存在，那么我们可以转移从 \(f[i - j]\) 转移到 \(f[i]\)。状态转移方程如下：

\[ f[i] = \min(f[i], f[i - j] + \textit{cost}[k]) \]

其中 \(\textit{cost}[k]\) 表示长度为 \(j\) 的单词且哈希值与 \(\textit{target}[i - j + 1, i]\) 相同的单词的最小代价。

时间复杂度 \(O(n \times \sqrt{L})\)，空间复杂度 \(O(n)\)。其中 \(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
class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        base, mod = 13331, 998244353
        n = len(target)
        h = [0] * (n + 1)
        p = [1] * (n + 1)
        for i, c in enumerate(target, 1):
            h[i] = (h[i - 1] * base + ord(c)) % mod
            p[i] = (p[i - 1] * base) % mod
        f = [0] + [inf] * n
        ss = sorted(set(map(len, words)))
        d = defaultdict(lambda: inf)
        min = lambda a, b: a if a < b else b
        for w, c in zip(words, costs):
            x = 0
            for ch in w:
                x = (x * base + ord(ch)) % mod
            d[x] = min(d[x], c)
        for i in range(1, n + 1):
            for j in ss:
                if j > i:
                    break
                x = (h[i] - h[i - j] * p[j]) % mod
                f[i] = min(f[i], f[i - j] + d[x])
        return f[n] if f[n] < 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
54
55
56
57
58
59
60
61
62
class Hashing {
    private final long[] p;
    private final long[] h;
    private final long mod;

    public Hashing(String word, long base, int mod) {
        int n = word.length();
        p = new long[n + 1];
        h = new long[n + 1];
        p[0] = 1;
        this.mod = mod;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * base % mod;
            h[i] = (h[i - 1] * base + word.charAt(i - 1)) % mod;
        }
    }

    public long query(int l, int r) {
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
}

class Solution {
    public int minimumCost(String target, String[] words, int[] costs) {
        final int base = 13331;
        final int mod = 998244353;
        final int inf = Integer.MAX_VALUE / 2;

        int n = target.length();
        Hashing hashing = new Hashing(target, base, mod);

        int[] f = new int[n + 1];
        Arrays.fill(f, inf);
        f[0] = 0;

        TreeSet<Integer> ss = new TreeSet<>();
        for (String w : words) {
            ss.add(w.length());
        }

        Map<Long, Integer> d = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            long x = 0;
            for (char c : words[i].toCharArray()) {
                x = (x * base + c) % mod;
            }
            d.merge(x, costs[i], Integer::min);
        }

        for (int i = 1; i <= n; i++) {
            for (int j : ss) {
                if (j > i) {
                    break;
                }
                long x = hashing.query(i - j + 1, i);
                f[i] = Math.min(f[i], f[i - j] + d.getOrDefault(x, inf));
            }
        }

        return f[n] >= inf ? -1 : f[n];
    }
}

 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
class Hashing {
private:
    vector<long> p, h;
    long mod;

public:
    Hashing(const string& word, long base, long mod)
        : p(word.size() + 1, 1)
        , h(word.size() + 1, 0)
        , mod(mod) {
        for (int i = 1; i <= word.size(); ++i) {
            p[i] = p[i - 1] * base % mod;
            h[i] = (h[i - 1] * base + word[i - 1]) % mod;
        }
    }

    long query(int l, int r) {
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
};

class Solution {
public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        const int base = 13331;
        const int mod = 998244353;
        const int inf = INT_MAX / 2;

        int n = target.size();
        Hashing hashing(target, base, mod);

        vector<int> f(n + 1, inf);
        f[0] = 0;

        set<int> ss;
        for (const string& w : words) {
            ss.insert(w.size());
        }

        unordered_map<long, int> d;
        for (int i = 0; i < words.size(); ++i) {
            long x = 0;
            for (char c : words[i]) {
                x = (x * base + c) % mod;
            }
            d[x] = d.find(x) == d.end() ? costs[i] : min(d[x], costs[i]);
        }

        for (int i = 1; i <= n; ++i) {
            for (int j : ss) {
                if (j > i) {
                    break;
                }
                long x = hashing.query(i - j + 1, i);
                if (d.contains(x)) {
                    f[i] = min(f[i], f[i - j] + d[x]);
                }
            }
        }

        return f[n] >= inf ? -1 : f[n];
    }
};

 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
type Hashing struct {
    p   []int64
    h   []int64
    mod int64
}

func NewHashing(word string, base, mod int64) *Hashing {
    n := len(word)
    p := make([]int64, n+1)
    h := make([]int64, n+1)
    p[0] = 1
    for i := 1; i <= n; i++ {
        p[i] = p[i-1] * base % mod
        h[i] = (h[i-1]*base + int64(word[i-1])) % mod
    }
    return &Hashing{p, h, mod}
}

func (hs *Hashing) query(l, r int) int64 {
    return (hs.h[r] - hs.h[l-1]*hs.p[r-l+1]%hs.mod + hs.mod) % hs.mod
}

func minimumCost(target string, words []string, costs []int) int {
    const base = 13331
    const mod = 998244353
    const inf = math.MaxInt32 / 2

    n := len(target)
    hashing := NewHashing(target, base, mod)

    f := make([]int, n+1)
    for i := range f {
        f[i] = inf
    }
    f[0] = 0

    ss := make(map[int]struct{})
    for _, w := range words {
        ss[len(w)] = struct{}{}
    }
    lengths := make([]int, 0, len(ss))
    for length := range ss {
        lengths = append(lengths, length)
    }
    sort.Ints(lengths)

    d := make(map[int64]int)
    for i, w := range words {
        var x int64
        for _, c := range w {
            x = (x*base + int64(c)) % mod
        }
        if existingCost, exists := d[x]; exists {
            if costs[i] < existingCost {
                d[x] = costs[i]
            }
        } else {
            d[x] = costs[i]
        }
    }

    for i := 1; i <= n; i++ {
        for _, j := range lengths {
            if j > i {
                break
            }
            x := hashing.query(i-j+1, i)
            if cost, ok := d[x]; ok {
                f[i] = min(f[i], f[i-j]+cost)
            }
        }
    }

    if f[n] >= inf {
        return -1
    }
    return f[n]
}

 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
class Hashing {
    private p: bigint[];
    private h: bigint[];
    private mod: bigint;

    constructor(word: string, base: number, mod: number) {
        const n = word.length;
        this.mod = BigInt(mod);
        const b = BigInt(base);
        this.p = new Array(n + 1);
        this.h = new Array(n + 1);
        this.p[0] = 1n;
        this.h[0] = 0n;
        for (let i = 1; i <= n; i++) {
            this.p[i] = (this.p[i - 1] * b) % this.mod;
            this.h[i] = (this.h[i - 1] * b + BigInt(word.charCodeAt(i - 1))) % this.mod;
        }
    }

    public query(l: number, r: number): number {
        const res =
            (this.h[r] - ((this.h[l - 1] * this.p[r - l + 1]) % this.mod) + this.mod) % this.mod;
        return Number(res);
    }
}

function minimumCost(target: string, words: string[], costs: number[]): number {
    const base = 13331;
    const mod = 998244353;
    const inf = 1e9;
    const n = target.length;
    const hashing = new Hashing(target, base, mod);
    const f = new Array(n + 1).fill(inf);
    f[0] = 0;

    const ss = Array.from(new Set(words.map(w => w.length))).sort((a, b) => a - b);
    const d = new Map<number, number>();

    for (let i = 0; i < words.length; i++) {
        let x = 0n;
        const b = BigInt(base);
        const m = BigInt(mod);
        const word = words[i];
        for (let j = 0; j < word.length; j++) {
            x = (x * b + BigInt(word.charCodeAt(j))) % m;
        }
        const hashVal = Number(x);
        d.set(hashVal, Math.min(d.get(hashVal) ?? inf, costs[i]));
    }

    for (let i = 1; i <= n; i++) {
        for (const j of ss) {
            if (j > i) break;
            const x = hashing.query(i - j + 1, i);
            if (d.has(x)) {
                f[i] = Math.min(f[i], f[i - j] + d.get(x)!);
            }
        }
    }

    return f[n] >= inf ? -1 : f[n];
}

 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
use std::collections::{HashMap, BTreeSet};
use std::cmp::min;

struct Hashing {
    p: Vec<i64>,
    h: Vec<i64>,
    mod_val: i64,
}

impl Hashing {
    fn new(word: &str, base: i64, mod_val: i64) -> Self {
        let n = word.len();
        let mut p = vec![0; n + 1];
        let mut h = vec![0; n + 1];
        p[0] = 1;
        let chars: Vec<u8> = word.bytes().collect();
        for i in 1..=n {
            p[i] = p[i - 1] * base % mod_val;
            h[i] = (h[i - 1] * base + chars[i - 1] as i64) % mod_val;
        }
        Hashing { p, h, mod_val }
    }

    fn query(&self, l: usize, r: usize) -> i64 {
        (self.h[r] - self.h[l - 1] * self.p[r - l + 1] % self.mod_val + self.mod_val) % self.mod_val
    }
}

impl Solution {
    pub fn minimum_cost(target: String, words: Vec<String>, costs: Vec<i32>) -> i32 {
        let base = 13331i64;
        let mod_val = 998244353i64;
        let inf = i32::MAX / 2;
        let n = target.len();
        let hashing = Hashing::new(&target, base, mod_val);

        let mut f = vec![inf; n + 1];
        f[0] = 0;

        let mut ss = BTreeSet::new();
        for w in &words {
            ss.insert(w.len());
        }

        let mut d = HashMap::new();
        for i in 0..words.len() {
            let mut x = 0i64;
            for c in words[i].bytes() {
                x = (x * base + c as i64) % mod_val;
            }
            let entry = d.entry(x).or_insert(inf);
            *entry = min(*entry, costs[i]);
        }

        for i in 1..=n {
            for &j in &ss {
                if j > i {
                    break;
                }
                let x = hashing.query(i - j + 1, i);
                if let Some(&cost) = d.get(&x) {
                    f[i] = min(f[i], f[i - j] + cost);
                }
            }
        }

        if f[n] >= inf { -1 } else { f[n] }
    }
}

评论