---

1576. 替换所有的问号

• 标签：字符串
• 难度：简单

题目链接

• 1576. 替换所有的问号 - 力扣

题目大意

描述：给定一个由小写字母和 '?' 组成的字符串 $s$。将每个 '?' 替换成一个小写字母，要求最终字符串中没有相邻的相同字符。

要求：返回任意一种有效结果。

说明：

• $1 \le s.length \le 100$。

示例：

• 示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

• 示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

解题思路

思路 1：模拟

1. 核心思想

从左到右遍历，遇到 '?' 时依次尝试 'a'、'b'、'c'，选第一个与前后字符都不相同的字母替换。

相邻位置最多各排除 $1$ 个字母，三个候选字母中必有可行解，无需遍历全部 $26$ 个字母。

2. 具体步骤

第 1 步：将 $s$ 转为字符列表 chars。

第 2 步：遍历每个位置 $i$：

• 若 chars[i] != '?'，跳过。
• 否则依次尝试 $ch \in \{\texttt{'a'}, \texttt{'b'}, \texttt{'c'}\}$：
  • 左邻合法：$i = 0$ 或 chars[i - 1] != ch。
  • 右邻合法：$i = n - 1$ 或 chars[i + 1] != ch。
  • 两者均满足则令 chars[i] = ch 并停止尝试。

第 3 步：返回 ''.join(chars)。

3. 举例说明

示例 1：$s = \texttt{"?zs"}$

$i$	字符	操作
$0$	?	试 'a'：左无、右 'z'，可行 → 替换为 'a'
$1$	z	跳过
$2$	s	跳过

结果："azs"。

示例 2：$s = \texttt{"ubv?w"}$

$i$	字符	操作
$0$	u	跳过
$1$	b	跳过
$2$	v	跳过
$3$	?	试 'a'：左 'v'、右 'w' 均不同 → 替换为 'a'
$4$	w	跳过

结果："ubvaw"（替换成 'v' 或 'w' 会与相邻字符重复，故 'a' 为可行解）。

连续 ? 的情况：$s = \texttt{"??yw"}$

$i$	字符	操作
$0$	?	试 'a'：右邻为 '?'，不冲突 → 替换为 'a'
$1$	?	试 'a'：左 'a' 冲突；试 'b'：左 'a'、右 'y' 均不同 → 替换为 'b'
$2$	y	跳过
$3$	w	跳过

结果："abyw"。后一个 ? 替换时已能利用前一个位置的实际字符，因此按序处理即可。

思路 1：代码

class Solution:
    def modifyString(self, s: str) -> str:
        chars = list(s)
        n = len(chars)
        for i in range(n):
            if chars[i] == '?':
                for ch in 'abc':
                    if (i == 0 or chars[i - 1] != ch) and \
                       (i == n - 1 or chars[i + 1] != ch):
                        chars[i] = ch
                        break
        return ''.join(chars)

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。