LeetCode如何替换所有问号

在LeetCode的编程挑战中，经常会遇到一些字符串处理的问题。其中一个常见的问题是要求替换字符串中的所有问号（?）为其他字符，同时确保替换后的字符串满足某些特定条件。本文将详细探讨如何解决这类问题，并通过一个具体的LeetCode题目来演示解决方案。

问题描述

假设我们有一个字符串s，其中包含若干个问号（?）。我们的任务是将所有的问号替换为小写字母（a到z），并且要求替换后的字符串中没有任何两个相邻的字符是相同的。换句话说，替换后的字符串中不能有连续的两个相同字符。

示例

• 输入: s = "?zs"

• 输出: "azs" 或 "bzs" 等

• 输入: s = "ubv?w"

• 输出: "ubvaw" 或 "ubvbw" 等

解决思路

要解决这个问题，我们需要遍历字符串中的每个字符，并在遇到问号时选择一个合适的字符来替换它。选择替换字符时，我们需要确保它与前后相邻的字符都不相同。

步骤

1. 遍历字符串：从左到右遍历字符串中的每个字符。
2. 遇到问号：当遇到问号时，选择一个合适的字符来替换它。
3. 选择替换字符：选择一个与前后字符都不相同的字符。通常可以选择a到z中的任意一个字符，只要它不等于前后字符即可。
4. 更新字符串：将问号替换为选择的字符，并继续遍历下一个字符。
5. 返回结果：遍历完成后，返回替换后的字符串。

代码实现

以下是使用Python实现的代码示例：

def replace_question_marks(s: str) -> str:
    s = list(s)  # 将字符串转换为列表，方便修改
    n = len(s)
    for i in range(n):
        if s[i] == '?':
            # 选择与前后字符都不相同的字符
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if (i == 0 or c != s[i-1]) and (i == n-1 or c != s[i+1]):
                    s[i] = c
                    break
    return ''.join(s)

# 测试用例
print(replace_question_marks("?zs"))  # 输出: "azs" 或 "bzs" 等
print(replace_question_marks("ubv?w"))  # 输出: "ubvaw" 或 "ubvbw" 等

代码解释

1. 转换为列表：我们将字符串s转换为列表，因为字符串在Python中是不可变的，而列表是可变的，方便我们修改字符。
2. 遍历字符：我们使用for循环遍历字符串中的每个字符。
3. 遇到问号：当遇到问号时，我们进入一个内部循环，尝试选择一个合适的字符来替换它。
4. 选择字符：我们遍历a到z，选择一个与前后字符都不相同的字符。如果当前字符是第一个字符（i == 0），则只需要确保它与下一个字符不相同；如果当前字符是最后一个字符（i == n-1），则只需要确保它与前一个字符不相同；否则，需要确保它与前后字符都不相同。
5. 替换字符：一旦找到合适的字符，我们将其替换到问号的位置，并跳出内部循环。
6. 返回结果：最后，我们将列表转换回字符串并返回。

复杂度分析

• 时间复杂度：O(n)，其中n是字符串的长度。我们只需要遍历字符串一次，并且在每个问号处最多尝试26次（a到z）。
• 空间复杂度：O(n)，因为我们使用了列表来存储字符串的字符。

总结

通过上述方法，我们可以有效地替换字符串中的所有问号，并确保替换后的字符串中没有连续相同的字符。这个问题虽然看似简单，但涉及到了字符串遍历、字符替换以及条件判断等多个编程基础知识点。掌握这类问题的解决方法，对于提升编程能力和应对LeetCode挑战非常有帮助。

希望本文对你理解如何替换字符串中的问号有所帮助，并能够在LeetCode的编程挑战中取得更好的成绩！