Kimi K2.6 快速 LeetCode 3213. 最小代价构造字符串 Go实现

LeetCode 3213. 最小代价构造字符串Construct String with Minimum Cost的 Go 实现核心思路是字符串哈希 动态规划这是该题最经典且高效的解法。---解题思路核心思想字符串哈希 DP1. 预处理 target 的前缀哈希使用滚动哈希在 O(n) 时间内构建前缀哈希数组 h 和幂次数组 p从而可以在 O(1) 时间内查询任意子串的哈希值。2. 预处理 words 的哈希值计算每个 words[i] 的哈希值存入 map。相同字符串只保留最小花费。3. 动态规划设 f[i] 为构造 target 前 i 个字符的最小花费。- 状态转移枚举 words 中出现过的所有长度 len若 target[i-len, i-1] 的哈希值匹配某个 word则 f[i] min(f[i], f[i-len] cost)。4. 优化只枚举 words 中出现过的长度集合避免无效枚举。时间复杂度O(n \times \sqrt{L})其中 n 为 target 长度L 为所有 words 长度之和。空间复杂度O(n)。---Go 代码实现gopackage mainimport (mathsort)// Hashing 滚动哈希结构体type Hashing struct {p []int64 // 前缀幂次h []int64 // 前缀哈希mod int64 // 模数}// NewHashing 创建新的哈希对象func NewHashing(word string, base, mod int64) *Hashing {n : len(word)p : make([]int64, n1)h : make([]int64, n1)p[0] 1for i : 1; i n; i {p[i] p[i-1] * base % modh[i] (h[i-1]*base int64(word[i-1])) % mod}return Hashing{p, h, mod}}// query 查询子串 [l, r] 的哈希值1-based闭区间func (hs *Hashing) query(l, r int) int64 {return (hs.h[r] - hs.h[l-1]*hs.p[r-l1]%hs.mod hs.mod) % hs.mod}func minimumCost(target string, words []string, costs []int) int {const base 13331const mod 998244353const inf math.MaxInt32 / 2n : len(target)hashing : NewHashing(target, base, mod)// f[i] 表示构造 target 前 i 个字符的最小花费f : make([]int, n1)for i : range f {f[i] inf}f[0] 0// 收集 words 中所有出现过的长度去重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)// 计算每个 word 的哈希值相同字符串保留最小花费d : make(map[int64]int)for i, w : range words {var x int64for _, 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-j1, 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]}---关键点说明要点 说明哈希冲突 使用单哈希模数 998244353基数 13331在 LeetCode 上通常可通过。若担心冲突可改用双哈希。相同字符串处理 d map 中相同哈希值只保留最小花费避免重复计算。长度枚举优化 用 map 去重 sort 排序只枚举实际出现过的长度大幅减少无效循环。1-based 索引 query(l, r) 使用 1-based 闭区间与 DP 数组 f[i]前 i 个字符对应。---示例验证输入target abcdef, words [abdef,abc,d,def,ef], costs [100,1,1,10,5]- f[3] f[0] cost(abc) 0 1 1- f[4] f[3] cost(d) 1 1 2- f[6] f[4] cost(ef) 2 5 7输出7 ✓---另一种解法后缀数组Go 标准库Go 标准库 index/suffixarray 提供了后缀数组实现可以直接使用代码更简洁goimport (index/suffixarraymath)func minimumCost(target string, words []string, costs []int) int {minCost : map[string]uint16{}for i, w : range words {c : uint16(costs[i])if minCost[w] 0 {minCost[w] c} else {minCost[w] min(minCost[w], c)}}n : len(target)type pair struct{ l, cost uint16 }from : make([][]pair, n1)sa : suffixarray.New([]byte(target))for w, c : range minCost {for _, l : range sa.Lookup([]byte(w), -1) {r : l len(w)from[r] append(from[r], pair{uint16(l), c})}}f : make([]int, n1)for i : 1; i n; i {f[i] math.MaxInt / 2for _, p : range from[i] {f[i] min(f[i], f[p.l]int(p.cost))}}if f[n] math.MaxInt/2 {return -1}return f[n]}两种方法均可通过哈希法更通用后缀数组法在 Go 中代码更简洁。