Kimi K2.6 快速 LeetCode 3213. 最小代价构造字符串 Go实现
LeetCode 3213. 最小代价构造字符串（Construct String with Minimum Cost）的 Go 实现，核心思路是字符串哈希 + 动态规划，这是该题最经典且高效的解法。
---
解题思路
核心思想：字符串哈希 + DP
1. 预处理 `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 代码实现
```go
package main
import (
"math"
"sort"
)
// 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, 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}
}
// query 查询子串 [l, r] 的哈希值（1-based，闭区间）
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[i] 表示构造 target 前 i 个字符的最小花费
f := make([]int, n+1)
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 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]
}
```
---
关键点说明
要点 说明
哈希冲突 使用单哈希（模数 `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` 提供了后缀数组实现，可以直接使用，代码更简洁：
```go
import (
"index/suffixarray"
"math"
)
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, n+1)
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, n+1)
for i := 1; i <= n; i++ {
f[i] = math.MaxInt / 2
for _, 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 中代码更简洁。