欢迎阅读 欢迎来到「替换所有的问号」题解之旅本文将带你从给问号填上不撞邻居的字母这一直观场景出发深入理解贪心 边界防护的巧妙运用并掌握如何逐个问号试填 26 个字母来构造出合法的最终字符串。在开始之前建议你先了解题目背景这是 LeetCode 1576 题给定含小写字母和?的字符串s把所有?替换成字母使得任意相邻两个字符都不相同返回任意一个合法结果。本质上每个?只需避开左右邻居问题转化为逐位贪心试填。明确学习目标掌握逐位贪心 邻居校验技术理解下标越界防护i 0/i n-1的必要性并熟练处理首尾问号与连续问号等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如s ?zs输出azss ubv?w输出ubvaw。本文将从问题转化、贪心试填、邻居校验、边界防护到代码实现层层递进。即使你对贪心还不熟悉我们也会从逐个问号填一个跟邻居都不一样的字母这一直觉出发让你轻松抓住核心思想——逐个试填只要不撞邻居。现在让我们一起填满问号构造合法字符串吧 ✏️愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》 钱塘江上潮信来今日方知我是我✨当前学习内容《模拟》一.题目1576. 替换所有的问号 - 力扣LeetCode​二、算法分析一、问题分析前置分析题目要求把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[i1])才可采用边界位置自动跳过不存在的邻居。填上并跳出s[i] ch; break;找到即填无需继续试。返回遍历结束返回s。 示例s ?zs等待填?使相邻不同步骤is[i]试填 ch左邻居 s[i-1]右邻居 s[i1]校验结果i00?a无i0za ! z✅s azsi11z———非问号跳过—i22s———非问号跳过—最终得到azs✅相邻a-z、z-s均不同与题目示例一致示例输出azs任何合法答案均可。三、正确性说明简单版本约束局部性每个?的合法性只取决于它左右两个邻居而填值不会影响其他?的邻居关系填完就固定因此逐位贪心不影响全局最优局部合法即全局合法。必然存在可填字母任一位置最多被左右邻居占用2 个字母边界处最多 1 个而字母表有26 个必然至少有一个字母可用贪心不会填不出来。校验条件完整(i 0 || ch ! s[i-1])保证不与左邻居相同首字符无左邻居短路跳过(i n-1 || ch ! s[i1])保证不与右邻居相同末字符无右邻居——两个条件合起来恰好覆盖相邻不同的全部要求。顺序填不影响正确性从左往右填右边的?校验时会看到已被填好的左侧字符非?校验依然有效不会因为填值顺序出错。 例子连续问号如何被依次化解s ???i0时无左邻居、右邻居是?未填a 满足条件 → 填 ai1时左邻居 a、右邻居?试 a 撞左邻居 → 试 b 通过 → 填 bi2时左邻居 b试 a 通过 → 填 a得到aba。每个问号都只避开已确定的邻居连续问号被逐个化解最终相邻全不同 ✅。四、实现细节边界防护初始化n s.size()直接原地修改s。边界防护i 0与i n-1的短路判断是防越界的核心——若漏掉i 0 ||i0时访问s[-1]会越界UB若漏掉i n-1 ||in-1时访问s[n]越界。用||短路自动跳过不存在的邻居。关键操作if (s[i] ?)识别待填位置、(i 0 || ch ! s[i-1]) (i n-1 || ch ! s[i1])邻居校验、s[i] ch; break;填值并终止试填。 例子首尾问号的边界处理s ?单字符n1i0既是首又是尾两个条件都短路为真第一个字母 a 直接通过→ 返回as ?ai0时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) { // 边界防护i0 时无左邻居、in-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]越界UBi n-1时s[i1]即s[n]越界。靠||的短路特性i 0为真时直接跳过后半部分的越界访问。若把顺序写反成ch ! s[i-1] || i 0短路失效先访问s[-1]照样越界——短路判断的顺序不可颠倒。难点2右边的?会不会影响当前校验ch ! s[i 1] // s[i1] 可能是 ?当右邻居还是?时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[i1]在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合法。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨