Kimi LeetCode 3474. 字典序最小的生成字符串 Go实现

LeetCode 3474. 字典序最小的生成字符串 — Go 实现解题思路1. 处理 T 约束遍历 str1对每个 T 位置将 str2 填入结果字符串的对应窗口。若同一位置被不同 T 要求填入不同字符则直接返回空串。2. 填充 a所有未被 T 固定的位置先填入 a保证字典序最小。3. 处理 F 约束从左到右检查每个 F 窗口。若该窗口恰好等于 str2则从右往左找到第一个非固定位置将其字符加 1如 a→b使窗口不再等于 str2且对字典序影响最小。若窗口全为固定位置且等于 str2则返回空串。Go 代码gofunc generateString(str1 string, str2 string) string {n : len(str1)m : len(str2)total : n m - 1ans : make([]byte, total)fixed : make([]bool, total)// 1. 处理所有 T 约束for i : 0; i n; i {if str1[i] T {for j : 0; j m; j {pos : i jif fixed[pos] ans[pos] ! str2[j] {return }ans[pos] str2[j]fixed[pos] true}}}// 2. 验证所有 T 约束无遗漏for i : 0; i n; i {if str1[i] T {for j : 0; j m; j {if ans[ij] ! str2[j] {return }}}}// 3. 未确定位置填充 a字典序最小for i : 0; i total; i {if !fixed[i] {ans[i] a}}// 4. 处理所有 F 约束for i : 0; i n; i {if str1[i] F {match : truefor j : 0; j m; j {if ans[ij] ! str2[j] {match falsebreak}}if !match {continue}// 窗口等于 str2需修改最右侧非固定位置found : falsefor j : m - 1; j 0; j-- {pos : i jif !fixed[pos] {ans[pos] // a-b, b-c...found truebreak}}if !found {return }}}return string(ans)}复杂度分析- 时间复杂度O(n \times m)其中 n \leq 10^4, m \leq 500最多约 5 \times 10^6 次操作。- 空间复杂度O(n m)用于存储结果字符串和固定标记数组。