替换空格

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

这道题目如果使用库函数将很简单

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll("\\s","%20");
    }
}

但是这种写法只适合平时工作，面试并不推荐，面试考察的一般不是使用轮子的能力。
下面我们来看看怎么造这个轮子～

方法一：

还是老套路，牺牲空间换时间

public class Solution {
    public static String replaceSpace(StringBuffer str) {
        StringBuilder res = new StringBuilder();
        String s = str.toString();
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) != ' ')
              res.append(s.charAt(i));
            else
                res.append("%20");
        }
        return res.toString();
    }
}

时间复杂度O（N），空间复杂度O（N）

方法二：

还是我们的老朋友，牺牲时间换空间。
通常的思路下，我们会构造一个循环，从头开始遍历数组，循环里套一个循环，用来将扫描到的空格之后的元素后移，便于插入“％20”。这样的时间复杂度为O（N^2)。由于代码比较简单这里就不再列出。这种方法的缺点是很容易超时，因为时间特性确实很差。

方法三：

那么有没有既有较好的空间复杂度同时又保证了时间复杂的算法呢？
其实方法二之所以时间特性很差，是因为存在很多重复移动，有的元素在遇到第一个空格时被后移了，在遇到第二个空格时仍要被后移。那么突破点就在这里，有没有办法减少重复计算呢？我们发现，重复计算的数量与空格数量密切相关，那么我们只需要获得空格总数，便得到了最终的数组长度。这时候从后往前扫描，将每个字符移动到自己对应的位置，每个字符仅需要移动一次便实现了我们的要求。（若从前往后扫描则又陷入了重复计算的坑）

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int spacenum = 0;//spacenum为计算空格数
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' ')
                spacenum++;
        }
        int indexold = str.length()-1; //indexold为为替换前的str下标
        int newlength = str.length() + spacenum*2;//计算空格转换成%20之后的str长度
        int indexnew = newlength-1;//indexold为为把空格替换为%20后的str下标
        str.setLength(newlength);//使str的长度扩大到转换成%20之后的长度,防止下标越界
        for(;indexold>=0 && indexold<newlength;--indexold){  
                if(str.charAt(indexold) == ' '){  //
                str.setCharAt(indexnew--, '0');
                str.setCharAt(indexnew--, '2');
                str.setCharAt(indexnew--, '%');
                }else{
                    str.setCharAt(indexnew--, str.charAt(indexold));
                }
        }
        return str.toString();
    }
}

时间复杂度O（N），空间复杂度O（1）