LeetCode 补充题 11. 翻转URL字符串里的单词

约 5 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节跳动 高频面试题
标签
字符串
目录

题目描述

✅ 补充题 11. 翻转URL字符串里的单词

题意分析

给一段 URL 里的字符串，其中的空格已经按百分号编码写成了 %20。要求把单词的先后顺序颠倒过来，单词内部保持原样，输出仍然用 %20 作为分隔符。例如 I%20am%20here 应得到 here%20am%20I。

这道题的形状和「翻转单词顺序」完全一致，唯一被改动的是分隔符的定义：从一个字符变成了三个字符的固定子串。这一处改动带来的连锁反应才是考点——判断「当前位置是不是分隔符」不再是一次字符比较，而是一次长度为 3 的子串匹配；跳过分隔符也不再是下标减一，而是减三。凡是把分隔符当成单字符处理的写法，在这里全部失效。

另一个要注意的地方是 % 在原串里只可能作为 %20 的一部分出现（题目语境是已编码的 URL），所以匹配 %20 不会遇到「半个分隔符」的歧义；但连续出现多个 %20（对应原文里的连续空格）是完全可能的，切分后会产生空片段，必须过滤掉，否则输出里会冒出连着的 %20%20。

边界要盯住：字符串可能以 %20 开头或结尾（对应前导、尾随空格），此时首尾会切出空片段；整个串可能全是 %20，结果应为空串；只有一个单词时输出就是它本身，前后不能挂上多余的 %20。

解法：按 %20 切分后逆序拼接

核心思路

%20 虽由三个字符组成，但在本题中只是固定分隔符。直接按它切分字符串，过滤前导、尾随或连续分隔符产生的空片段，再把非空单词逆序拼接即可；不需要先解码 URL 再重新编码。

不变量：过滤后的 words 按原顺序、不重不漏地保存全部非空单词。逆序遍历它并仅在已有输出时添加 %20，便能同时保证单词顺序反转、单词内容不变，且结果首尾没有分隔符。

解题步骤

  1. 使用标准库按 %20 切分输入。
  2. 丢弃空片段，只保留真实单词。
  3. 从后向前遍历单词；结果非空时先追加一个 %20，再追加当前单词。
  4. 没有非空单词时自然返回空串。

例如 %20I%20%20am%20here%20 过滤后得到 [I, am, here]，逆序拼接为 here%20am%20I。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public String reverseWords(String s) {
        String[] parts = s.split("%20");
        List<String> words = new ArrayList<>();
        for (String part : parts) {
            if (!part.isEmpty()) {
                words.add(part);
            }
        }

        StringBuilder answer = new StringBuilder();
        for (int i = words.size() - 1; i >= 0; i--) {
            if (answer.length() > 0) {
                answer.append("%20");
            }
            answer.append(words.get(i));
        }
        return answer.toString();
    }
}

import "strings"

func reverseWords(s string) string {
    parts := strings.Split(s, "%20")
    words := make([]string, 0, len(parts))
    for _, part := range parts {
        if part != "" {
            words = append(words, part)
        }
    }

    for left, right := 0, len(words)-1; left < right; left, right = left+1, right-1 {
        words[left], words[right] = words[right], words[left]
    }
    return strings.Join(words, "%20")
}

复杂度分析

  • 时间复杂度：$O(n)$。切分、过滤、反转和拼接处理的字符总量都是线性的。
  • 空间复杂度：$O(n)$。切分结果、单词列表和返回字符串都与输入长度同阶。

关键点总结

  • 把 %20 当作完整分隔符，而不是分别处理 %、2、0。
  • 过滤空片段可统一处理首尾分隔符与连续分隔符。
  • 只在结果非空时添加分隔符，避免首尾多出 %20。
  • 标准库已经可靠完成固定子串切分，无须手写解析器或 URL 解码流程。

易错点总结

  • 先做通用 URL 解码：可能连其他百分号编码一起改动，超出题目范围。
  • 按单个字符切分：%20 是一个整体，按 % 或普通空格切分都会破坏单词。
  • 不丢弃空片段：a%20%20b 会错误保留两个连续分隔符。
  • 每个单词后都追加分隔符：空输入或最后一个单词会留下多余的 %20。
  • 反转整个字符串：会把单词内部字符也反转。

相似题目

题目 难度 考察点
151. 反转字符串中的单词 中等 分隔符是单个空格且可能连续，进阶还要求 $O(1)$ 额外空间原地完成
剑指 Offer 58 - I. 翻转单词顺序 简单 与 151 同题，是本题把分隔符换成单字符后的原型
186. 反转字符串中的单词 II 中等 保证无多余空格，必须原地用「整体反转 + 逐词反转」两步完成
557. 反转字符串中的单词 III 简单 只反转单词内部而保留单词顺序，恰好与本题的要求相反
71. 简化路径 中等 同样按分隔符切分再过滤空片段，但之后要用栈处理 . 与 .. 的层级语义
344. 反转字符串 简单 双指针原地反转的基础零件，本题 Go 版的单词交换就是它的数组版
8. 字符串转换整数 (atoi) 中等 同为手写字符串解析，重点在状态转移与溢出判断而非顺序调整
58. 最后一个单词的长度 简单 只需从右往左找出第一个单词，可用来单独练分隔符跳过的写法