替换空格

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

解析
需要将一个字节的“空格”替换成三个字节的“%20”
首先，String类提供了replaceAll(regex, replacement)的方法，可以直接调用。

另外，可以考虑new一个新的StringBuffer，遍历传过来的字符串，依次向新的StringBuffer中append()，遇到“空格”，则append("%20")，遍历完成return即可。

而看了讨论区大佬们的思路，才恍然大悟。这类算法题最重要的就是节省时间和空间。
思路是在不新分配空间的前提下，将字符串从后向前遍历并替换，减少字符的移动。
首先，先遍历一遍字符串，记录字符串长度和字符串空格的个数，根据这两个可以计算出替换后的字符串的长度，并给字符串设置替换后的长度；然后，倒序遍历字符串，使用StringBuffer.setCharAt(index, ch)方法从末尾set，遇到“空格”，就连续set'0'，'2'，'%'。（主要在遍历和set时，老字符串长度和新字符串长度都要-1，不然会数组越界）

Java

/**
 * 用String类的replaceAll()方法
 * 运行时间：23ms
 * 占用内存：9256k
 */
public String repalceSpace1(StringBuffer str) {
    return str.toString().replaceAll(" ", "%20");
}

/**
 * 创建一个新对象存储
 * 运行时间：26ms
 * 占用内存：9572k
 */
public String repalceSpace2(StringBuffer str) {
    StringBuffer result = new StringBuffer();
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (c == ' ') {
            result.append("%20");
        } else {
            result.append(c);
        }
    }
    return result.toString();
}

/**
 * 先遍历一遍记录替换后的长度，从后往前替换，减少移动
 * 运行时间：20ms
 * 占用内存：9412k
 */
public String repalceSpace3(StringBuffer str) {
    if (str == null || str.length() <= 0) {
        return "";
    }
    //老数组长度
    int oldLength = 0;
    //空格数
    int spaceNum = 0;
    for (int i = 0; i < str.length(); i++) {
        oldLength++;
        if (str.charAt(i) == ' ') {
            spaceNum++;
        }
    }
    //新数组长度
    int newLength = oldLength + spaceNum * 2;
    //设置数组长度为新
    str.setLength(newLength);
    int oldIndex = oldLength - 1;
    int newIndex = newLength - 1;
    while (oldIndex >= 0 && newLength > oldLength) {
        if (str.charAt(oldIndex) == ' ') {
            str.setCharAt(newIndex--, '0');
            str.setCharAt(newIndex--, '2');
            str.setCharAt(newIndex--, '%');
        } else {
            str.setCharAt(newIndex--, str.charAt(oldIndex));
        }
        oldIndex--;
    }
    return str.toString();
}

Python

Python则直接提供了replace()方法

class Solution:
    # 运行时间：25ms
    # 占用内存：5640k
    def replaceSpace(self, s):
        return s.replace(' ', '%20')

if __name__ == '__main__':
    a = Solution()
    print(a.replaceSpace('We are family'))