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

以下是 LeetCode 3474. 字典序最小的生成字符串 的 Python3 实现附详细思路说明。---题目概述给定两个字符串 str1长度 n仅含 T/F和 str2长度 m小写字母需要构造一个长度为 n m - 1 的字符串 word满足- 若 str1[i] T则 word[i:im] str2- 若 str1[i] F则 word[i:im] ! str2返回字典序最小的 word无解则返回 。---解题思路贪心构造核心策略分三步第一步处理所有 T 约束遍历 str1对每个 T 位置 i将 str2 填入 word[i:im]。如果某个位置已被填入且与当前要填的字符冲突说明无解直接返回 。被 T 确定的位置标记为不可修改。第二步填充剩余位置为 a为了字典序最小所有未定位置先填 a。第三步处理所有 F 约束遍历 str1对每个 F 位置 i- 如果 word[i:im] 已经不等于 str2无需处理。- 如果等于 str2则必须修改窗口内至少一个字符。为了字典序影响最小选择窗口中最右侧的可修改位置将其改为 b比 a 大的最小字符。若窗口内没有可修改位置说明无解返回 。 为什么选最右侧因为字典序中左侧字符权重更高修改靠右的位置对整体字典序影响最小。---Python3 代码pythonclass Solution:def generateString(self, str1: str, str2: str) - str:n len(str1)m len(str2)sz n m - 1# ans[i] None 表示尚未确定ans [None] * sz# 标记每个位置是否被T约束固定不可修改fixed [False] * sz# 1. 处理所有 T 约束for i in range(n):if str1[i] T:for j in range(m):pos i jif ans[pos] is not None and ans[pos] ! str2[j]:# 冲突无解return ans[pos] str2[j]fixed[pos] True# 2. 剩余位置填 a保证字典序最小for i in range(sz):if ans[i] is None:ans[i] a# 3. 处理所有 F 约束for i in range(n):if str1[i] F:# 检查当前窗口是否等于 str2match Truefor j in range(m):if ans[i j] ! str2[j]:match Falsebreakif not match:continue # 已经满足不等于跳过# 窗口等于 str2需要修改。找最右侧可修改位置mod_pos -1for j in range(m - 1, -1, -1):if not fixed[i j]:mod_pos i jbreakif mod_pos -1:# 没有可修改位置无解return # 改成 b比 a 大的最小字符ans[mod_pos] b# 修改后该位置也变为不可修改避免被后续F再次改动导致前功尽弃fixed[mod_pos] Truereturn .join(ans)---复杂度分析指标 复杂度时间 O(n × m) — 最多三次遍历每次涉及长度为 m 的窗口操作空间 O(n m) — 结果数组和标记数组---示例验证输入 输出 说明str1TFTF, str2ab ababa T填ab剩余填aF处子串ba≠ab满足str1TFTF, str2abc T约束冲突无解str1F, str2d a 填a后子串a≠d满足该解法在 LeetCode 上已验证通过。