Easy

题目描述

给定一个字符串 s，其中仅包含小写英文字母和 ‘?’ 字符，将所有的 ‘?’ 字符替换为小写字母，使得最终的字符串不包含任何连续重复字符。你不能修改非 ‘?’ 字符。

保证给定字符串中除了 ‘?’ 外没有连续重复字符。

在完成所有转换（可能为零次）后，返回最终字符串。如果有多个解决方案，返回其中任何一个即可。可以证明在给定约束下总是存在答案。

示例 1:

输入：s = "?zs"
输出："azs"
解释：这个问题有 25 种解决方案。从 "azs" 到 "yzs"，都是有效的。只有 "z" 是无效的修改，因为字符串会变成 "zzs"，包含连续重复字符。

示例 2:

输入：s = "ubv?w"
输出："ubvaw"
解释：这个问题有 24 种解决方案。只有 "v" 和 "w" 是无效的修改，因为字符串会变成 "ubvvw" 和 "ubvww"，包含连续重复字符。

约束：

  • 1 <= s.length <= 100
  • s 由小写英文字母和 ‘?’ 组成

解题思路

这是一个贪心算法问题。核心思路是从左到右遍历字符串，遇到 ‘?’ 时，找到一个字符使其与左右相邻的字符都不相同。

解题思路：

  1. 线性扫描：从左到右遍历字符串
  2. 贪心选择：对于每个 ‘?’，我们需要选择一个字符，使其与左右相邻字符都不同
  3. 字符选择策略：由于只需要避开最多2个字符（左边和右边），而我们有26个小写字母可选，所以总能找到合适的字符
  4. 实现细节：
    • 检查左边字符（如果存在且已处理过）
    • 检查右边字符（如果存在）
    • 选择第一个不等于这两个字符的字母（通常是 ‘a’, ‘b’, ‘c’ 中的一个）

时间复杂度分析： 每个位置最多检查3个字符（‘a’, ‘b’, ‘c’），由于字符集有限，可以认为是常数时间，总体时间复杂度为 O(n)。

空间复杂度分析： 如果允许原地修改，空间复杂度为 O(1)；否则需要 O(n) 空间存储结果。

代码实现

class Solution {
public:
    string modifyString(string s) {
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '?') {
                for (char c = 'a'; c <= 'z'; c++) {
                    bool valid = true;
                    // 检查左边字符
                    if (i > 0 && s[i-1] == c) {
                        valid = false;
                    }
                    // 检查右边字符
                    if (i < n-1 && s[i+1] == c) {
                        valid = false;
                    }
                    if (valid) {
                        s[i] = c;
                        break;
                    }
                }
            }
        }
        
        return s;
    }
};

class Solution:
    def modifyString(self, s: str) -> str:
        s = list(s)  # 转换为可修改的列表
        n = len(s)
        
        for i in range(n):
            if s[i] == '?':
                for c in 'abc':  # 通常前三个字母就够了
                    valid = True
                    # 检查左边字符
                    if i > 0 and s[i-1] == c:
                        valid = False
                    # 检查右边字符
                    if i < n-1 and s[i+1] == c:
                        valid = False
                    if valid:
                        s[i] = c
                        break
        
        return ''.join(s)

public class Solution {
    public string ModifyString(string s) {
        char[] chars = s.ToCharArray();
        int n = chars.Length;
        
        for (int i = 0; i < n; i++) {
            if (chars[i] == '?') {
                for (char c = 'a'; c <= 'z'; c++) {
                    bool valid = true;
                    // 检查左边字符
                    if (i > 0 && chars[i-1] == c) {
                        valid = false;
                    }
                    // 检查右边字符
                    if (i < n-1 && chars[i+1] == c) {
                        valid = false;
                    }
                    if (valid) {
                        chars[i] = c;
                        break;
                    }
                }
            }
        }
        
        return new string(chars);
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var modifyString = function(s) {
    let chars = s.split('');
    let n = chars.length;
    
    for (let i = 0; i < n; i++) {
        if (chars[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历字符串一次，每个位置最多检查3个字符
空间复杂度O(1) 或 O(n)原地修改为O(1)，创建新字符串为O(n)