👋 欢迎阅读
🎯 欢迎来到「替换所有的问号」题解之旅！ 本文将带你从"给问号填上不撞邻居的字母"这一直观场景出发，深入理解贪心 + 边界防护的巧妙运用，并掌握如何逐个问号试填 26 个字母来构造出合法的最终字符串。
在开始之前，建议你先：
-
了解题目背景：这是 LeetCode 1576 题，给定含小写字母和
?的字符串s，把所有?替换成字母，使得任意相邻两个字符都不相同，返回任意一个合法结果。本质上，每个?只需避开左右邻居，问题转化为逐位贪心试填。 -
明确学习目标：掌握逐位贪心 + 邻居校验技术，理解下标越界防护
i == 0/i == n-1的必要性，并熟练处理首尾问号与连续问号等边界情况。 -
准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如
s = "?zs"输出"azs"，s = "ubv?w"输出"ubvaw"）。
本文将从问题转化、贪心试填、邻居校验、边界防护到代码实现，层层递进。即使你对贪心还不熟悉，我们也会从"逐个问号填一个跟邻居都不一样的字母"这一直觉出发，让你轻松抓住核心思想——逐个试填，只要不撞邻居。现在，让我们一起填满问号，构造合法字符串吧！ ✏️🎯
🔥 愿旖旎 · 个人主页
📘 学习专栏： 《算法专栏》《LangChain学习》《贪心算法》
🌄 钱塘江上潮信来，今日方知我是我
✨当前学习内容：《模拟》
一.题目
二、算法分析
一、问题分析（前置分析）
- 题目要求：把
s中所有?替换为小写字母，使任意相邻字符都不相同，返回任一合法结果。 - 关键约束：字母仅 26 个；相邻必须不同；首位/末位只有一个邻居。
- 核心思路：每个
?的约束只与左右两个邻居有关，互不影响，因此可以逐位贪心：从小到大试字母，第一个与左右邻居都不同的即可采用——由于 26 个字母中最多只有 2 个被邻居占用，必然存在可填字母，贪心不会失败。
📌 例子：为什么"最多试三次"就够了
s = "?a?"：第一个?只需避开右邻居a，试到b即可（?左邻居不存在）；第二个?只需避开左邻居a，试到b即可 →"bab"。每个问号的左右邻居最多占 2 个字母，26 个字母里至少还有 24 个可选，所以"从小到大试"必定能在前几个字母内找到答案，这是贪心必然成功的根本原因。
二、算法策略
核心步骤：
- 遍历字符串：
i从 0 到n-1。 - 遇到问号则试填：
ch从'a'试到'z'。 - 邻居校验：满足
(i == 0 || ch != s[i-1]) && (i == n-1 || ch != s[i+1])才可采用（边界位置自动跳过不存在的邻居）。 - 填上并跳出：
s[i] = ch; break;（找到即填，无需继续试）。 - 返回：遍历结束返回
s。
📊 示例（s = "?zs"，等待填 ? 使相邻不同）：
| 步骤 | i | s[i] | 试填 ch | 左邻居 s[i-1] | 右邻居 s[i+1] | 校验 | 结果 |
|---|---|---|---|---|---|---|---|
| i=0 | 0 | ? | 'a' | 无（i==0） | 'z' | a != z ✅ | s = "azs" |
| i=1 | 1 | 'z' | — | — | — | 非问号，跳过 | — |
| i=2 | 2 | 's' | — | — | — | 非问号，跳过 | — |
最终得到 "azs" ✅（相邻 a-z、z-s 均不同），与题目示例一致（示例输出 "azs"，任何合法答案均可）。
三、正确性说明（简单版本）
- 约束局部性：每个
?的合法性只取决于它左右两个邻居，而填值不会影响其他?的邻居关系（填完就固定），因此逐位贪心不影响全局最优，局部合法即全局合法。 - 必然存在可填字母：任一位置最多被左右邻居占用 2 个字母（边界处最多 1 个），而字母表有 26 个，必然至少有一个字母可用，贪心不会填不出来。
- 校验条件完整：
(i == 0 || ch != s[i-1])保证不与左邻居相同（首字符无左邻居，短路跳过）；(i == n-1 || ch != s[i+1])保证不与右邻居相同（末字符无右邻居）——两个条件合起来恰好覆盖"相邻不同"的全部要求。 - 顺序填不影响正确性：从左往右填，右边的
?校验时会看到已被填好的左侧字符（非?），校验依然有效，不会因为填值顺序出错。
📌 例子：连续问号如何被依次化解
s = "???"：i=0时无左邻居、右邻居是?（未填），'a' 满足条件 → 填 'a'；i=1时左邻居 'a'、右邻居?，试 'a' 撞左邻居 → 试 'b' 通过 → 填 'b'；i=2时左邻居 'b'，试 'a' 通过 → 填 'a'，得到"aba"。每个问号都只避开已确定的邻居，连续问号被逐个化解，最终相邻全不同 ✅。
四、实现细节（边界防护）
- 初始化：
n = s.size()，直接原地修改s。 - 边界防护：
i == 0与i == n-1的短路判断是防越界的核心——若漏掉i == 0 ||，i=0时访问s[-1]会越界（UB）；若漏掉i == n-1 ||，i=n-1时访问s[n]越界。用||短路自动跳过不存在的邻居。 - 关键操作：
if (s[i] == '?')（识别待填位置）、(i == 0 || ch != s[i-1]) && (i == n-1 || ch != s[i+1])（邻居校验）、s[i] = ch; break;（填值并终止试填）。
📌 例子：首尾问号的边界处理
s = "?"（单字符）：n=1，i=0既是首又是尾，两个条件都短路为真，第一个字母 'a' 直接通过 → 返回"a"；s = "?a"：i=0时i == 0短路（无左邻居），只需ch != 'a'→ 填 'b' →"ba"。首尾位置只有一个邻居，短路判断让同一套逻辑自然适配。
五、返回值（目标映射）
- 返回
s：替换所有问号后的合法字符串（任意一个合法解均可），对应题目"返回最终的字符串（若有多种解法，返回任一）"。
三.代码
class Solution
{
public:
string modifyString(string s)
{
int n = s.size();
// 1. 遍历字符串，逐个处理问号
for (int i = 0; i < n; i++)
{
if (s[i] == '?')
{
// 2. 从小到大试字母，找到第一个不与左右邻居冲突的
for (char ch = 'a'; ch <= 'z'; ch++)
{
// 边界防护：i==0 时无左邻居、i==n-1 时无右邻居，用 || 短路跳过
if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1]))
{
s[i] = ch; // 填上合法字母
break; // 找到即可，无需继续尝试
}
}
}
}
return s; // 3. 返回替换后的字符串
}
};四、易错点分析
难点1：边界校验必须用 || 短路
if ((i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1]))
i == 0时s[i-1]即s[-1]（越界，UB）；i == n-1时s[i+1]即s[n]（越界）。靠||的短路特性：i == 0为真时直接跳过后半部分的越界访问。若把顺序写反成ch != s[i-1] || i == 0，短路失效（先访问s[-1]），照样越界——短路判断的顺序不可颠倒。
难点2：右边的 ? 会不会影响当前校验
ch != s[i + 1] // s[i+1] 可能是 '?'当右邻居还是
?时，ch != '?'恒成立（字母不可能等于问号），相当于不做限制——这是安全的：右邻居稍后填值时会主动避开当前位置的字符，两者不可能冲突。同理左邻居若是?（未填），后续也会避开。"未填位置不构成约束" 是本解法能一遍扫完的关键。
难点3：原地修改与遍历顺序的配合
s[i] = ch; // 原地修改从左往右填，左侧必然已经全部确定（要么原本是字母，要么已在本轮填好），所以校验
s[i-1]时读到的是最终值，判断有效。若改成从右往左填，则要保证右侧已确定——两个方向都可行，但必须保证"已确定的一侧"被正确校验；从左往右是最自然的顺序。
五、流程图
🎯 闭幕
🎉 恭喜你完成了「替换所有的问号」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀 动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。
💡 深入思考
-
代码对每个
'?'从'a'到'z'依次尝试，找到第一个不与左右邻居冲突的字符。为什么最多尝试 3 个字母就一定能找到合法字符？ 如果字母表只有 2 个字母，还能保证有解吗？ -
边界判断使用了
(i == 0 || ch != s[i - 1]) && (i == n - 1 || ch != s[i + 1])。为什么必须用||短路？ 如果直接写ch != s[i-1] && ch != s[i+1]，在i == 0或i == n-1时会发生什么？ -
如果字符串中存在 连续多个
'?'（如"???"），当前算法能否正确处理？为什么修改前面的'?'不会影响后面'?'的合法性判断？ 请举例说明。
如果你觉得本文对你有所帮助，欢迎：
👍 点赞 / 收藏
👤 关注作者，获取更多题解
💬 留言交流你的疑问或优化思路
📌 深入思考答案
-
最多尝试 3 个字母 是因为每个
'?'最多只有左右两个邻居，只要字母表大小 ≥ 3，就一定能找到一个既不同于左邻居又不同于右邻居的字符。若字母表只有 2 个字母，则可能无解（例如"a?a"，中间不能是a，只能是b，但若字母表只有{a,b}，b与左右都不同，其实可以；但若"a?b"且字母表只有{a,b}，则?不能是a也不能是b，无解）。 -
必须用
||短路，否则i == 0时访问s[-1]会越界，i == n-1时访问s[n]也会越界。短路运算保证在边界情况下跳过越界访问。 -
连续多个
'?'能正确处理，因为每次只修改当前'?'，且只与左右已确定的字符比较。修改后，该位置变成确定字符，后续'?'再比较时，左邻居就是刚刚填好的字符，逻辑依然成立。例如"???"，第一个填'a'，第二个不能是'a'填'b'，第三个不能是'b'填'a'，得到"aba"，合法。
祝你在 算法之路 上越走越稳，早日攻克每一道难题！下次见 🚀✨
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2601_96587588/article/details/166838618
