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