LeetCode 面试题 01.03. URL化
题目描述
题意分析
将字符串前
length个字符中的每个空格替换为%20，其他字符保持原样。length是真实内容长度，之后的字符只是预留空间，不属于需要转换的内容。题目保证尾部有足够空间容纳扩张后的结果，并明确要求 Java 使用字符数组直接操作。下面先说明顺序构建的思路，再给出利用预留空间、从后向前写入的字符数组解法。
解法：线性扫描 + 构建结果字符串
核心思路
[!blue]
每个字符的输出只取决于它是否为空格，与相邻字符无关。建立输出缓冲，从左到右扫描真实内容：空格追加三个字符
%20，非空格追加自身。处理完前i个字符时，缓冲里恰好就是这个前缀转换后的结果，因此扫描结束便得到完整答案。扫描上界必须使用
length，不能使用整个字符串的物理长度。真实内容里的首尾空格和连续空格都是有效内容，需要逐个替换；只有length之后的预留字符应被忽略，不能用裁剪首尾空格来区分两者。
解题步骤
- 建立空输出缓冲区。
- 只扫描前 length 个字符。
- 空格追加 %20，其他字符追加自身。
- 返回缓冲区内容。
length == 0时没有有效字符，结果为空串。Go 的缓冲初始化为长度零、容量length，之后通过append增长；容量只是预分配空间，不能把它误设为已经存在的输出长度。
代码实现
class Solution {
public String replaceSpaces(String S, int length) {
StringBuilder sb = new StringBuilder();
// 只读取真实内容长度，忽略后面的预留字符。
for (int i = 0; i < length; i++) {
char c = S.charAt(i);
if (c == ' ') {
sb.append("%20");
} else {
sb.append(c);
}
}
return sb.toString();
}
}
func replaceSpaces(S string, length int) string {
buf := make([]byte, 0, length)
// 只读取真实内容长度，忽略后面的预留字符。
for i := 0; i < length; i++ {
if S[i] == ' ' {
buf = append(buf, '%', '2', '0')
} else {
buf = append(buf, S[i])
}
}
return string(buf)
}
复杂度分析
- 时间复杂度：$O(length+1)$，每个有效字符产生至多三个字符。
- 空间复杂度：$O(length+1)$，保存结果缓冲。
关键点总结
[!green]
- 真实内容长度决定读取边界。
- 每个空格单独展开，连续空格不能合并。
- 顺序追加避免在字符串中间反复插入。
解法二：字符数组从后向前替换
核心思路
[!blue]
先把字符串转换为可修改的字符数组或字节切片，只统计前
length个位置中的空格数spaces。每个空格由一个字符变成三个字符，多占两个位置，所以结果长度是newLength = length + 2 * spaces，题目保证原数组能容纳它。如果从前往后直接扩张，写入的
%20可能覆盖尚未读取的内容。因此用read从真实内容末尾向前读，用write从结果末尾向前写。普通字符写入一个位置；空格在末尾三个位置写入%20，然后把写指针向前移动三格。处理当前位置前，
write - read等于尚未处理部分中空格数的两倍，所以写指针不会落在读指针左侧。遇到空格时，这个差值至少为二，写入的三个位置也都不早于当前读位置，不会覆盖未读取的前缀。两指针向左推进后，已经写好的后缀正是原内容对应后缀的转换结果，直到全部读完。最后只取数组前
newLength个字符作为结果，不能把仍未使用的尾部预留空间一起返回。这里是在转换得到的可变数组内部完成替换；字符串参数本身不可修改。
解题步骤
- 将
S转换为可变数组，统计真实内容中的空格数。- 算出结果长度，初始化读指针和写指针。
- 从后向前读取，普通字符写一次，空格写成
%20。- 返回前
newLength个字符组成的字符串。
代码实现
class Solution {
public String replaceSpaces(String S, int length) {
char[] chars = S.toCharArray();
int spaces = 0;
for (int i = 0; i < length; i++) {
if (chars[i] == ' ') {
spaces++;
}
}
int newLength = length + 2 * spaces;
int write = newLength - 1;
for (int read = length - 1; read >= 0; read--) {
if (chars[read] == ' ') {
chars[write--] = '0';
chars[write--] = '2';
chars[write--] = '%';
} else {
chars[write--] = chars[read];
}
}
return new String(chars, 0, newLength);
}
}
func replaceSpaces(S string, length int) string {
buf := []byte(S)
spaces := 0
for i := 0; i < length; i++ {
if buf[i] == ' ' {
spaces++
}
}
newLength := length + 2*spaces
write := newLength - 1
for read := length - 1; read >= 0; read-- {
if buf[read] == ' ' {
buf[write] = '0'
buf[write-1] = '2'
buf[write-2] = '%'
write -= 3
} else {
buf[write] = buf[read]
write--
}
}
return string(buf[:newLength])
}
复杂度分析
时间复杂度：$O( S + 1)$，包含把整个字符串转换为数组；实际扫描和替换只处理真实内容及其扩张结果。
空间复杂度：$O( S + 1)$，当前字符串接口需要可变数组及返回字符串。若输入本来就是具有足够预留空间的字符数组，替换过程本身只需 $O(1)$ 额外空间。
关键点总结
[!green]
- 先统计空格，才能确定扩张后写入的终点。
- 从后向前写入，利用
write >= read保护未读取的前缀。- 只返回扩张后的有效长度，不返回多余预留字符。
易错点总结
[!yellow]
- 处理整个 S：把预留空白也替换进结果。
- 先 trim：真实内容的首尾空格被丢掉。
- 空格替换后又追加原空格：输出多出字符。
- Go 缓冲初始化为非零长度再 append：结果前面会多出默认零字节。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 05. 替换空格 | 简单 | 空格替换规则相同，本题只处理真实长度前的内容，尾部预留区不能当成待替换字符。 |
| 1089. 复写零 | 简单 | 同样涉及输出扩张，但原题直接修改固定数组并截断，本题结果必须覆盖全部真实内容。 |