📃 题目描述

题目链接：剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

🔔 解题思路

暴力解法，新建一个数组存储替换后的结果，遍历原数组，遇到空格就填入 %20，不是空格就直接填入原字符就行时间复杂度 O(N), 空间复杂度 O(N)

还有一种双指针解法：具体思路如下：

1. 遍历原数组统计空格数量

2. 扩充字符串长度（+ 空格数量 * 2）

   由于 Java 中 String 是不可变数组，所以此处我们不得不新建一个数组 or StringBuilder 用来进行字符串的扩充，所以这种方法的空间复杂度对于 Java 语言来说其实还是 O(N)

3. 定义双指针：left: 原数组长度 - 1，right: 扩充后的长度 - 1

4. 从后往前遍历：

   1. 如果左指针遇到空格，右指针依次填入 %20
   2. 如果左指针遇到字符，直接将左指针的值赋给右指针

5. 左指针和右指针还有分别左移 1 格继续遍历处理

class Solution {
    public String replaceSpace(String s) {
        if (s == null || s.length() == 0) {
            return s; 
        }
		
        // 空格的个数
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                count ++;
            }
        }

        char[] res = new char[s.length() + count * 2];
        for (int i = 0; i < s.length(); i ++) {
            res[i] = s.charAt(i);
        }

        int i = s.length() - 1;
        int j = res.length - 1;

        while (i >= 0) {
            if (s.charAt(i) == ' ') {
                res[j --] = '0';
                res[j --] = '2';
                res[j --] = '%';
            }
            else {
                res[j --] = s.charAt(i);
            }

            i --;
        }

        return new String(res);
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)