LeetCode 剑指 Offer 05. 替换空格
目录
题目描述
给定一个字符串，逐个替换字符串中的空格为
%20。请注意，返回的字符串应该是一个新的字符串，原字符串不变。示例 1： 输入：
s = "We are happy."输出："We%20are%20happy."示例 2： 输入：
s = " Hello World! "输出："Hello%20World!"提示：
- 0 <= s.length <= 10000
题意分析
输入一个字符串，把其中每个空格换成三个字符
%20，返回一个新串，原串保持不变。除了空格，其余字符原样保留，字符之间的相对顺序也不变。「返回新字符串、原串不变」这个约束否定了原地双指针的经典写法：那种写法要求容器可以扩容，而 Java 的 String、Go 的 string 都是不可变的，只能另开缓冲区写结果。
长度上限只有一万，且每个空格最多变成三个字符，结果长度不超过原长的三倍，几十 KB 的量级，说明不需要任何压缩技巧，一次线性构造就足够；真正被考察的是「知不知道反复拼接字符串会退化」。
边界有两个：空串要返回空串而不是抛异常；整串没有空格时结果应与原串完全一致，构造过程不能额外添加或丢失字符。
解法：一次遍历构造新字符串
核心思路
最容易想到的写法是
res = res + c这样逐字符累加。它的问题在于字符串不可变，每次+都要新建一个数组并把已有内容整体复制一遍，n 个字符累计复制量是 $1 + 2 + \dots + n$，退化成 $O(n^2)$，字符串长一点就会明显变慢。观察到瓶颈完全来自「结果容器不可变」，而不是遍历本身，于是换一个可变的容器：Java 用 StringBuilder，Go 用
[]byte切片，追加操作摊还是 $O(1)$，最后一次性转成字符串。进一步还能省掉扩容开销：结果长度至少是 n，所以按 n 预留容量即可让扩容次数从对数级降到最多几次。
由此得到扫描时维护的不变量：处理完前 i 个字符后，缓冲区里存放的恰好是
s[0..i)的完整替换结果。每读入一个字符只做一次追加，不回头修改已写入的内容，所以循环结束时 i = n，缓冲区自然就是整串的答案。需要留意的是编码单位：
%20是 ASCII，空格也是 ASCII，因此在 Go 里可以放心按字节遍历，多字节的中文字符不会被误判成空格——UTF-8 的续字节最高位恒为 1，永远不可能等于 0x20。
解题步骤
- 建一个可变缓冲区，并按
s.length()预设初始容量。预留容量不是为了正确性，而是避免在追加过程中反复扩容复制。- 从左到右遍历每个字符。之所以可以单向一次走完，是因为替换是「局部的」：某个位置换不换只取决于它自己，不依赖上下文，也不影响别的位置。
- 当前字符是空格就追加
%20，否则原样追加该字符。这一步保证了不变量在每轮之后仍然成立。- 遍历结束把缓冲区转成字符串返回。原串自始至终没有被写过，天然满足「原字符串不变」。
以
s = "We are happy."走一遍：缓冲区初始为空。读W，非空格，缓冲区变成W；读e，变成We；读到空格，追加三个字符，变成We%20；接着a、r、e依次追加，变成We%20are；再读到第二个空格，变成We%20are%20；随后h、a、p、p、y追加成We%20are%20happy；最后读到.，它不是空格，原样追加，缓冲区为We%20are%20happy.。遍历到此结束，转成字符串返回，与期望输出一致。顺带验证边界：
s = ""时循环一次都不进，返回空串；s = "abc"时每一轮都走 else 分支，返回abc，与原串相同。
代码实现
class Solution {
public String replaceSpace(String s) {
StringBuilder builder = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ') {
builder.append("%20");
} else {
builder.append(c);
}
}
return builder.toString();
}
}
func replaceSpace(s string) string {
res := make([]byte, 0, len(s))
for i := 0; i < len(s); i++ {
if s[i] == ' ' {
res = append(res, '%', '2', '0')
} else {
res = append(res, s[i])
}
}
return string(res)
}
复杂度分析
- 时间复杂度：$O(n)$，每个字符只被读一次、写一次，追加操作摊还常数；预留容量后扩容复制的总代价也是线性的。
- 空间复杂度：$O(n)$，缓冲区长度介于 n 与 3n 之间，属于必要的输出空间；除此之外只有下标和临时字符等常数级变量。
关键点总结
- 字符串不可变的语言里，循环中用
+拼接是典型的隐藏 $O(n^2)$，任何按字符构造结果的题都应该条件反射地换成可变缓冲区。- 结果长度有上界时提前预留容量，是把「摊还线性」变成「几乎无扩容」的低成本优化，写一行就能说明你懂底层扩容机制。
- 替换类问题先判断是否「局部可决定」：若某位置的输出只由该位置的输入决定，就一定能单向一次遍历完成，不需要回溯或两趟扫描。
- 按字节处理 ASCII 分隔符在 UTF-8 下是安全的，因为多字节序列的每个字节最高位都是 1，这条性质在 Go 里经常被用来避免昂贵的 rune 解码。
- 面试视角：这题真正的考点是原题背景——C++ 里给定足够大的字符数组要求原地替换，标准答案是「先统计空格数算出新长度，再从后往前双指针填充」，避免前移时覆盖未处理的数据。即使本题签名返回新串，也要主动把这个从后往前的思路讲出来，面试官等的就是它。
易错点总结
- 错误写法：在循环里用
res += c拼接字符串 → 用例长度一万且几乎全是空格的串，累计复制量达到亿级字符，本该几毫秒的题目跑到秒级甚至超时。- 错误写法：把空格判成
c == '\0'或用Character.isWhitespace(c)→ 用例s = "a\tb"，制表符被当成空格替换成a%20b，题目只要求替换半角空格。- 错误写法：Java 里写成
builder.append('%20')用单引号 → 单引号只能容纳一个字符，代码根本编译不过。- 错误写法：Go 里写成
res = append(res, "%20")→[]byte不能直接追加 string，编译报错；必须写append(res, '%', '2', '0')或append(res, "%20"...)。- 错误写法：遍历条件写成
i <= len(s)→ 用例s = "ab"，最后一轮访问下标 2 越界，Go 直接 panic，Java 抛 StringIndexOutOfBoundsException。- 错误写法：预留容量时写
make([]byte, len(s))而不是make([]byte, 0, len(s))→ 用例s = "ab"，切片一上来就有两个零字节，追加后结果是"\x00\x00ab"，前面多出两个空字符。- 错误写法：先
s = strings.TrimSpace(s)再替换 → 用例s = " a b "，首尾空格被吞掉，返回a%20b，正确答案是%20a%20b%20。- 错误写法：把返回值写成缓冲区本身而忘记转换，例如 Go 里
return res→ 函数签名要求 string，返回[]byte编译不通过；Java 里忘记toString()则返回类型不匹配。- 错误写法：为空串加一句
if (s == null || s.isEmpty()) return null;→ 用例s = ""，返回 null 而不是空串，判题直接判错，而循环本身对空串已经天然正确，这个特判纯属多余。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 01.03. URL化 | 简单 | 同一替换逻辑，但给定真实长度，考察从后往前的原地填充 |
| 443. 压缩字符串 | 中等 | 结果只会变短，需要读写双指针原地覆盖并返回新长度 |
| 面试题 01.06. 字符串压缩 | 简单 | 需要与原串比长度，压缩后不变短则返回原串 |
| 剑指 Offer 58 - II. 左旋转字符串 | 简单 | 长度不变只挪位置，可用三次反转做到 $O(1)$ 额外空间 |
| 557. 反转字符串中的单词 III | 简单 | 要先按空格切分出单词边界，再在段内做反转 |
| 151. 反转字符串中的单词 | 中等 | 需要处理连续空格与首尾空格，输出时单词间只留一个空格 |