5.替换空格

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

解法思路：

补充： 本题也可以直击使用字符串的replaceAll()方法来处理

1. 如果函数的输入要求是String

1. 在 Python 和 Java 语言中，字符串都被设计成「不可变」的类型，即无法直接修改字符串的某一位字符，需要新建一个字符串实现。
   所以空间复杂度为O(n)

java,创建一个StringBuilder对象，命名为res，然后遍历字符串中的每个字符 c，java中使用charAt(index) 获取指定索引位置的字符
- 当 c 为空格时：向 res 后添加字符串 “%20” ；
- 当 c 不为空格时：向 res 后添加字符 c ；

最后将res.toString();

class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        for(Character c : s.toCharArray())
        {
            if(c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();
    }
}

复杂度分析：

• 时间复杂度 O(N) ： 遍历使用 O(N) ，每轮添加（修改）字符操作使用 O(1) ；
• 空间复杂度 O(N) ： Java 新建的 StringBuilder 都使用了线性大小的额外空间。

2. 如果函数的输入要求是StringBuidler

因为java中StringBuilder是可变的，那么就可以使用类似《剑指offer》中提供的扩充原字符串 + 双指针思路来处理。

先遍历原字符串，遇到空格，则在原字符串末尾 append 任意两个字符，如两个空格。

用指针 i 指向原字符串末尾，j 指向现字符串末尾，i, j 从后往前遍历，当 i 遇到空格，j 位置依次要赋值为 ‘0’,’2’,’%’，若不是空格，直接赋值为 i 指向的字符。

class Solution {

    /**
     * 将字符串中的所有空格替换为%20
     *
     * @param str 字符串
     * @return 替换后的字符串
     */
    public String replaceSpaces(StringBuffer str) {
        if (str == null) {
            return null;
        }

        int len = str.length();
        for (int i = 0; i < len; ++i) {
            if (str.charAt(i) == ' ') {
                str.append("  ");
            }
        }

        int i = len - 1, j = str.length() - 1;
        for (; i >= 0; --i) {
            char ch = str.charAt(i);
            if (ch == ' ') {
                str.setCharAt(j--, '0');
                str.setCharAt(j--, '2');
                str.setCharAt(j--, '%');
            } else {
                str.setCharAt(j--, ch);
            }
        }
        return str.toString();
    }
}

复杂度分析：

• 时间复杂度 O(N) ： 遍历使用 O(N) ，每轮添加（修改）字符操作使用 O(1) ；
• 空间复杂度 O(N) ： O(1)

注意： 为什么要从后向前遍历？

• 因为，如果从前向后遍历，空格替换为’%20’,是将一个字符替换为三个字符，后面需要处理覆盖移动的操作，最后一个空格后面的字符需要多次移动，
• 而从后向前，在扩展了原有字符长度的基础上，从后向前，每个字符只需要移动一次，减少了移动次数，提高了效率。

---

知识点

注意：， java中char字符是单引号’’,String字符串才是双引号””

String s="1234";
if (s.charAt(1)=='1') {
    System.out.println("1");
}

思路扩展：

在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。