6.1 模拟专题：LeetCode 1576. 更换全部的问号
1. 标题链接LeetCode 1576. 更换全部的问号
2. 标题形貌
给定一个仅包含小写字母和问号 '?' 的字符串 s，要求将全部 '?' 更换为任意小写字母，使得更换后的字符串中 没有相邻的两个字符相同。
示例：
[*]输入：s = "?zs" → 输出："azs"（第一个 '?' 更换为 'a'）。
[*]输入：s = "ubv?w" → 输出："ubvaw"（'?' 更换为 'a'）。
3. 示例分析
[*]简单更换：
[*]输入："a?b" → 输出："acb"（'?' 更换为 'c'）。
[*]边界处置惩罚：
[*]输入："??" → 输出："ab"（两个 '?' 分别更换为 'a' 和 'b'）。
[*]复杂更换：
[*]输入："a?a" → 输出："aba"（中间的 '?' 更换为 'b'）。
4. 算法思路
核心思想：
[*]遍历字符串：
[*]从左到右逐个字符处置惩罚，碰到 '?' 时进行更换。
[*]字符选择策略：
[*]从 'a' 到 'z' 依次尝试，选择第一个满足以下条件的字符：
[*]与左侧字符差异（若存在）。
[*]与右侧字符差异（若存在）。
[*]左右判断：
[*]每次更换只关注当前字符的左右邻人，确保局部最优，从而保证全局最优。
时间复杂度：O(n * 26) → O(n)，其中 n 为字符串长度。
空间复杂度：O(1)，无需额外空间。
5. 边界条件与留意事项
[*]边界处置惩罚：
[*]当 '?' 位于字符串开头时，只需保证与右侧字符差异。
[*]当 '?' 位于字符串末尾时，只需保证与左侧字符差异。
[*]字符范围：
[*]仅需更换为小写字母 'a'-'z'，无需处置惩罚其他字符。
[*]相邻字符辩论：
[*]若左右字符相同（如 "a?a"），中间的 '?' 必须选择一个与两者差异的字符。
6. 代码实现
class Solution {
public:
string modifyString(string s) {
for (int i = 0; i < s.size(); i++) {
if (s == '?') {
// 遍历 'a'-'z'，寻找可替换字符
for (char ch = 'a'; ch <= 'z'; ch++) {
bool leftOk = (i == 0) || (s != ch); // 左侧无冲突
bool rightOk = (i == s.size()-1) || (s != ch); // 右侧无冲突
if (leftOk && rightOk) {
s = ch;
break; // 找到第一个可行字符后立即终止
}
}
}
}
return s;
}
};
https://i-blog.csdnimg.cn/direct/9a078582bac24f4e82e440035c71708e.png
关键代码剖析
[*] 遍历字符串：
for (int i = 0; i < s.size(); i++)
[*]逐个字符查抄是否为 '?'。
[*] 字符更换逻辑：
for (char ch = 'a'; ch <= 'z'; ch++)
[*]从 'a' 到 'z' 依次尝试，找到第一个满足条件的字符。
[*] 条件查抄：
bool leftOk = (i == 0) || (s != ch);
bool rightOk = (i == s.size()-1) || (s != ch);
[*]leftOk：若 '?' 在开头，无需查抄左侧；否则查抄左侧字符是否差异。
[*]rightOk：若 '?' 在末尾，无需查抄右侧；否则查抄右侧字符是否差异。
[*] 更换并终止：
if (leftOk && rightOk) {
s = ch;
break;
}
[*]找到第一个可行字符后立刻更换并跳出循环，保证时间复杂度最优。
与其他解法的对比
方法时间复杂度空间复杂度核心思想模拟算法O(n)O(1)逐个更换，选择第一个可行字符预添补法O(n)O(1)预先处置惩罚全部 '?' 的位置随机更换法O(n)O(1)随机选择字符，大概需重试
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]