LeetCode 面试题 01.03. URL化

约 8 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节跳动 程序员面试金典（第 6 版）
标签
字符串
目录

题目描述

✅ 面试题 01.03. URL化

题意分析

给定字符串 S 和一个整数 length，length 表示 S 中"真实内容"的长度。要求把前 length 个字符里的每个空格替换成 %20 并返回结果。S 中下标 length 及其之后的字符是为容纳扩展而预留的尾部空白，不属于内容，必须整体丢弃。

约束里最关键的信号是同时给了 S 和 length 两个参数。如果只是"把空格换成 %20"，一个参数就够了；额外给 length，说明出题人希望你意识到字符串带有"逻辑长度"与"物理容量"的区别，这正是 CTCI 原题"就地从后往前填充"的引子——预留空间的大小恰好等于替换后需要的总长度。

边界上要覆盖：length == 0（返回空串）；length == S.length()（没有预留位，说明内容里本就没有空格）；内容里连续多个空格（每个都要独立展开成三个字符，不能按"一段空白"合并）；内容首尾就是空格（同样要替换，题目从未要求裁剪）。字符集只有大小写字母和空格，不涉及多字节编码，按字节处理是安全的。

解法：线性扫描 + 构建结果字符串

核心思路

暴力想法是反复做字符串替换：找到一个空格，把它删掉再插进三个字符。瓶颈很明显——字符串在多数语言里不可变，每替换一次都要整体拷贝，k 个空格就是 $O(nk)$，最坏退化成 $O(n^2)$；就算换成可变数组，中间插入也要搬移整个后缀。

观察到的关键点是：每个输入字符的输出完全独立。' ' 固定映射到 %、2、0 三个字符，其他字符固定映射到自身，前一个字符的处理结果不会改变后一个字符该怎么映射。既然没有跨字符依赖，就没有理由回头修改已经写好的部分——按序把每个字符的映射结果追加到输出缓冲区，一次扫描即可。

由此确定要维护的状态非常简单：一个只增不改的输出缓冲区 sb（Go 里是 buf）和扫描下标 i。不变量是"当外层循环处理完下标 i 后，缓冲区恰好等于 S[0..i] 这段前缀的正确 URL 化结果"。循环结束时 i 走到 length - 1，不变量直接给出整个答案。注意扫描上界取 length 而非 S.length()，这一步就把预留的尾部空白自然排除掉了。

还有一个值得在面试里主动提的变体：若题目改成"给定容量足够的字符数组，要求原地修改、不许开新数组"，则应改用从后往前的双指针——先数出空格个数算出新长度 newLen，写指针从 newLen - 1 出发、读指针从 length - 1 出发反向搬运。反向填充能保证写指针永远在读指针右侧，不会覆盖尚未读取的内容。本题返回的是新字符串，用正向追加更直白。

解题步骤

  • 建立输出缓冲区。Java 用 StringBuilder，Go 用 make([]byte, 0, length) 预分配容量。之所以要缓冲区而不是不断做字符串拼接，是因为拼接每次都产生新对象，会把 $O(n)$ 的算法拖成 $O(n^2)$；缓冲区追加是均摊 $O(1)$。
  • 让循环上界取 length 而不是 S.length()。这是本题最容易失分的一行。S 尾部那些预留位也是空格字符，如果扫到底，它们会被一并替换成 %20，答案凭空多出一大截。用 length 收口，等价于先做一次隐式截断。
  • 对每个字符做二选一的映射。S[i] == ' ' 时追加 "%20"，否则追加 S[i] 本身。这里用 if/else 而不是"先无条件追加再回头修补"，是为了让缓冲区保持"只追加不回退"的性质，从而保住线性复杂度。
  • 循环结束后把缓冲区转成字符串返回。此时不变量已覆盖 S[0..length-1] 全段，缓冲区内容就是最终答案，不需要任何后处理。

以 S = "Mr John Smith "、length = 13 走一遍：S 物理长度是 17，末尾 4 个空格是预留位，只处理前 13 个字符即 "Mr John Smith"。i = 0..1 读到 M、r，缓冲区为 "Mr"；i = 2 读到空格，追加三个字符，缓冲区为 "Mr%20"；i = 3..6 读到 J、o、h、n，缓冲区为 "Mr%20John"；i = 7 读到空格，缓冲区为 "Mr%20John%20"；i = 8..12 读到 S、m、i、t、h，缓冲区为 "Mr%20John%20Smith"。i 到达 13 循环终止，末尾那 4 个预留空格根本没被访问。返回 "Mr%20John%20Smith"，长度 17，恰好等于 S 的物理长度——这不是巧合，题目保证预留空间刚好够用，可以拿来做自检。

代码实现

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)$。只对前 length 个字符扫描一次，每个字符触发常数次追加；StringBuilder/append 的扩容是均摊 $O(1)$，不改变量级。
  • 空间复杂度：$O(length)$。输出缓冲区最坏情况（全是空格）是内容长度的 3 倍，仍与 length 同阶；除缓冲区外只用常数个变量。若题目要求原地修改，可以做到 $O(1)$ 额外空间。

关键点总结

  • "逻辑长度 + 物理容量"是字符串题的一类固定信号。只要函数签名里除了容器还多给一个长度参数，就要立刻警觉：容器尾部有不属于内容的填充位，所有循环边界都必须用逻辑长度而不是 size()。
  • 每个元素的输出只依赖自身时，一次正向追加就是最优解。判断"有没有跨元素依赖"是决定能否单趟扫描的通用准绳；有依赖才需要预处理、双指针或反向遍历。
  • 需要在原容器内扩张时改成从后往前填充。反向写入能保证写指针始终不越过读指针，是"数组内扩张"的标准手法，和 88. 合并两个有序数组 的收尾用的是同一个技巧。
  • 面试视角：主动区分"返回新串"和"原地改数组"两个版本。LeetCode 的签名返回 String，正向追加即可；但面试官问这题往往想听 CTCI 原版的原地解法。稳妥答法是先写正向版本保证正确，再口述"若要求 $O(1)$ 额外空间，我会先统计空格数得到新长度，然后双指针从后往前搬"，并说明反向的理由。
  • 避免在循环里做字符串拼接。s += x 在 Java/Go 里都会产生新对象，这是把线性算法写成平方级的最常见方式，面试官几乎必问一句"这里的复杂度是多少"。

易错点总结

  • 错误写法：for (int i = 0; i < S.length(); i++) → 用例 S = "Mr John Smith "、length = 13：尾部 4 个预留空格也被替换，返回 "Mr%20John%20Smith%20%20%20%20"，比正确答案多出 12 个字符，直接 WA。
  • 错误写法：return S.replace(" ", "%20") → 用例同上：不仅同样吞掉预留空格得到超长结果，而且完全绕开本题考点（逻辑长度截断 + 手工构建），面试里会被要求重写。
  • 错误写法：if (c == ' ') sb.append("%20"); sb.append(c);（漏掉 else） → 用例 S = "a b"、length = 3：空格被替换后又被原样追加，返回 "a%20 b"，多出一个空格。分支互斥时务必用 else，或在 if 内 continue。
  • 错误写法：String res = ""; res += c; 在循环里累加 → 用例 length = 500000 的同类大输入题：每次 += 触发一次全量拷贝，总代价 $O(n^2)$。本题数据小能过，但同样的习惯在 443. 压缩字符串 上直接 TLE。
  • 错误写法：先 S = S.trim() 再处理 → 用例 S = " a "、length = 3：内容本身以空格开头结尾，trim 把它们删掉，返回 "a" 而不是 "%20a%20"，少了两处替换。
  • 错误写法：把连续空白当成一段处理，只替换一次 → 用例 S = "a b"、length = 4：正确答案是 "a%20%20b"，合并处理会得到 "a%20b"，少一个 %20。
  • 错误写法：Go 里写 buf = append(buf, "%20") → 编译报错，[]byte 不能直接 append 字符串；必须写成 append(buf, '%', '2', '0') 或 append(buf, "%20"...)。
  • 错误写法：预分配写成 make([]byte, length)（第二个参数当成了容量） → 用例 S = "a b"、length = 3：切片一开始就有 3 个零字节，append 追加在其后，返回 "\x00\x00\x00a%20b"，前面多出三个空字符。必须写 make([]byte, 0, length)。
  • 错误写法：Java 里用 S.charAt(i) == " " 比较 → 编译失败，char 与 String 不可比较；正确写法是 == ' ' 这种字符字面量。
  • 错误写法：先按 S.length() 建缓冲区再在末尾 setLength(...) 裁剪 → 用例 S = "a b "、length = 3：裁剪长度需要按"内容长度 + 2 × 空格数"重新算，一旦算错（比如仍按 length 裁）会得到 "a%2"，把一个 %20 截断成两半。与其额外算一次长度，不如一开始就按 length 收口。

相似题目

题目 难度 考察点
剑指 Offer 05. 替换空格 简单 同样的空格展开，但不给逻辑长度，无需处理预留位
面试题 01.06. 字符串压缩 简单 输出可能变长也可能变短，需与原串比长度后决定返回哪个
443. 压缩字符串 中等 强制原地压缩并返回新长度，必须用读写双指针而非额外缓冲区
151. 反转字符串中的单词 中等 空格是分隔符而非待替换字符，重点在多余空白的归并与整体翻转