题目

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

示例 1：

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

限制：

0 <= s 的长度 <= 10000

要点

• 如果是直接从头查找，找到后替换，但是会挤到后面的元素，导致部分挪动，时间复杂度为O(n^2)
• 可以先计算替换后的整体长度，然后从后往前处理数据，避免了挤到其他元素，时间复杂度为O(n)

代码

public String replaceSpace(String s) {
        if(s.length()==0){
            return s;
        }
        int spaceCount=0;
        for (int i = 0; i < s.length(); i++) {
            if(' '==(s.charAt(i))){
                spaceCount++;
            }
        }
        int k=s.length()+spaceCount*2-1;
        char[] arr=new char[k+1];
        for (int i = s.length()-1; i >=0 ; i--) {
            if(' '==(s.charAt(i))){
                arr[k--]='0';
                arr[k--]='2';
                arr[k--]='%';
            }else{
                arr[k--]=s.charAt(i);
            }
        }
        return new String(arr);
    }