5. 替换空格

题目链接

Leetcode

题目描述

将一个字符串中的每个空格替换成 "%20"。

Input:
"A B"

Output:
"A%20B"

力扣上对应的 LCR 122“路径加密”改成了把 '.' 替换为空格，替换前后长度不变，代码见替换前后长度不变的情况。

解题思路

Java 的 String 不可变，最直接的做法是用 StringBuilder 逐个字符复制，遇到空格追加 "%20"，时间和空间复杂度都是 O(N)。

原题考查的是在原数组上替换，假设数组末尾有足够的空余位置。如果从前往后替换，每遇到一个空格，它后面的所有字符都要后移 2 位，最坏 O(N²)。从后往前填可以让每个字符只移动一次：

• 先统计空格个数，新长度 = 原长度 + 2 × 空格数；
• P1 指向原字符串的末尾，P2 指向新长度的末尾，P1 从后往前扫描：普通字符复制到 P2，空格则在 P2 处从后往前依次写入 '0'、'2'、'%'；
• P1 与 P2 相遇时，前面已经没有空格，结束。

以 "A B C" 为例（_ 表示空格），原长度 5，新长度 9：

下标          0  1  2  3  4  5  6  7  8
初始          A  _  B  _  C                P1 = 4，P2 = 8
复制 C        A  _  B  _  C           C    P1 = 3，P2 = 7
空格写 %20    A  _  B  _  C  %  2  0  C    P1 = 2，P2 = 4
复制 B        A  _  B  _  B  %  2  0  C    P1 = 1，P2 = 3
空格写 %20    A  %  2  0  B  %  2  0  C    P1 = 0，P2 = 0，相遇

public String replaceSpace(String s) {
    int spaces = 0;
    for (int i = 0; i < s.length(); i++)
        if (s.charAt(i) == ' ')
            spaces++;
    // 模拟末尾留有足够空间的字符数组
    char[] chars = Arrays.copyOf(s.toCharArray(), s.length() + 2 * spaces);
    int p1 = s.length() - 1, p2 = chars.length - 1;
    while (p1 >= 0 && p1 < p2) {
        char c = chars[p1--];
        if (c == ' ') {
            chars[p2--] = '0';
            chars[p2--] = '2';
            chars[p2--] = '%';
        } else {
            chars[p2--] = c;
        }
    }
    return new String(chars);
}

替换前后长度不变的情况

LCR 122 把 '.' 换成空格，一个字符换一个字符，不涉及移动，逐个复制即可。

public String pathEncryption(String path) {
    StringBuilder sb = new StringBuilder();
    for (char c : path.toCharArray()) {
        if (c == '.') {
            sb.append(' ');
        } else {
            sb.append(c);
        }
    }
    return sb.toString();
}