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

这是 LeetCode 3474. 字典序最小的生成字符串 的 Java 实现。解题思路核心思想贪心 三步构造法1. 先处理 T 约束遍历 str1对于每个 T 位置将 str2 填入答案数组的对应位置。如果某个位置已被填入且与新字符冲突直接返回空串。这些被 T 确定的位置标记为不可修改。2. 填充剩余位置为 a为了字典序最小所有未被 T 确定的位置先全部填 a。3. 处理 F 约束遍历 str1对于每个 F 位置检查对应子串是否等于 str2。如果相等说明违反了 F 约束需要修改。为了字典序影响最小选择该子串中最右侧的可修改位置将其改为 b比 a 大的最小字符。如果该子串中没有可修改位置返回空串。为什么选最右侧修改 因为字典序比较是从左到右的修改越靠右的位置对整体字典序的影响越小。Java 代码javaimport java.util.Arrays;class Solution {public String generateString(String str1, String str2) {final int n str1.length();final int m str2.length();final int sz n m - 1;char[] ans new char[sz];boolean[] modifiable new boolean[sz];Arrays.fill(modifiable, true);// 1. 先处理所有 T 位置for (int i 0; i n; i) {if (str1.charAt(i) T) {for (int j 0; j m; j) {final int pos i j;// 如果该位置已有字符且冲突则无解if (ans[pos] ! 0 ans[pos] ! str2.charAt(j)) {return ;}ans[pos] str2.charAt(j);modifiable[pos] false; // 被 T 固定不可修改}}}// 2. 剩余位置先全部填 a字典序最小for (int i 0; i sz; i) {if (ans[i] 0) {ans[i] a;}}// 3. 处理所有 F 位置for (int i 0; i n; i) {if (str1.charAt(i) F match(ans, i, str2)) {// 当前子串等于 str2违反 F 约束需要修改final int modifiablePos lastModifiablePosition(i, m, modifiable);if (modifiablePos -1) {return ; // 没有可修改位置无解}ans[modifiablePos] b; // 改为比 a 大的最小字符modifiable[modifiablePos] false; // 修改后也不再可变}}return new String(ans);}// 判断从位置 i 开始、长度为 m 的子串是否等于 str2private boolean match(char[] ans, int i, String s) {for (int j 0; j s.length(); j) {if (ans[i j] ! s.charAt(j)) {return false;}}return true;}// 找到从位置 i 开始、长度为 m 的子串中最右侧的可修改位置private int lastModifiablePosition(int i, int m, boolean[] modifiable) {int modifiablePos -1;for (int j 0; j m; j) {final int pos i j;if (modifiable[pos]) {modifiablePos pos;}}return modifiablePos;}}复杂度分析- 时间复杂度O(n \times m)其中 n \le 10^4, m \le 500最坏情况约 5 \times 10^6 次操作可以通过。- 空间复杂度O(n m)用于存储答案数组和可修改标记数组。