• 每日一题：LeetCode：1576.替换所有问号

  • 时间：2022-01-05

  • 力扣难度：Easy

  • 个人难度：Easy

  • 数据结构：字符串

  • 算法：数学、模拟

2022-01-05：LeetCode：1576.替换所有问号

1. 题目描述

• 题目：原题链接

  • 给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

  • 注意：不能修改非 '?' 字符。

  • 题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

  • 在完成所有转换（可能无需转换）后返回最终的字符串。

  • 如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

• 输入输出规范

  • 输入：字符串s

  • 输出：替换后的字符串

• 输入输出示例

  • 输入："???"

  • 输出："aba"

2. 方法：简单模拟

• 思路

  • 暴力模拟，遍历整个字符串，遇到"?"时需要获取其前后两个字符并比较是否重复

  • 判断时注意不要超出边界，对于首尾元素要单独判断

  • 由于是否连续仅需要和前后相邻的两个字符进行比较，所以无需构建小写字母的哈希表，直接用常量空间即可

  • 思考：本题对替换成的字母没有要求，任意小写字母即可，如果要求按照字典序优先替换要如何实现

• 复杂度分析：n是正整数的数值大小

  • 时间复杂度：O(26*n)

  • 空间复杂度：O(1)

• 题解

public String modifyString(String s) {
    if(s == null || s.length() == 0) return null;
    char[] chs = s.toCharArray();
    char ch;
    for(int i = 0; i < s.length(); i++) {
        if(chs[i] == '?') {
            ch = 'a';
            while((i - 1 >= 0 && chs[i - 1] == ch) || (i + 1 < s.length() && chs[i + 1] == ch)){
                ch++;
            }
            chs[i] =  (char) ch;

        }            
    }
    return String.valueOf(chs);
}

• 思考与优化

  • 思考：本题对替换成的字母没有要求，任意小写字母即可，如果要求按照字典序优先替换要如何实现

  • 优化：实际上，本题在替换时只需要判断三个连续的小写字母与字符串中"?"前后两个字符是否相同即可，无需用到全部26个小写字母

  • 因此可以优化循环内的判断和替换的部分，内层循环只需要遍历三个连续字母

  • 实际上，两种方式的真实复杂度是差不多的，因为前者的条件会使得其最多执行三次就跳出循环

• 复杂度分析：n是正整数的数值大小

  • 时间复杂度：O(3*n)，因为内层只遍历三个连续字母

  • 空间复杂度：O(1)

• 题解：优化版本

public String modifyString(String s) {
    if(s == null || s.length() == 0) return null;
    char[] chs = s.toCharArray();
    for(int i = 0; i < s.length(); i++) {
        for(int c = 0; c < 3 && chs[i] == '?'; c++) {
            if(i - 1 >= 0 && chs[i - 1] == c + 'a') continue;
            if(i + 1 < s.length() && chs[i + 1] == c +'a') continue;
            chs[i] = (char) (c + 'a');
        }
    }
    return String.valueOf(chs);
}