替换空格

题目：

请实现一个函数，把字符创中的每个空格替换成 “%20”。例如，输入 "We are happy."，则输出 "We%20are%20happy."

分析：

1. 首先想到的是遍历字符数组，然后把每个空格替换成 “%20”，这样的话每次把空格替换成三个字符，就需要把后面所有的字符向后移动三位。如果字符长度是n，对每个空格字符，需要移动后面 O(n) 个字符，因此对于含有 O(n) 个空格的字符串，时间复杂度就是 O(n*n)。
2. 我们可以先遍历一次数组，这样就能统计出其中空格个数，然后计算出替换完成之后的字符串长度。然后从字符串尾部开始复制和替换，前面的字符不用变动，可以节省时间。时间复杂度是 O(n)。

代码：

public class ReplaceSpaceInString {

    /**
     * 替换
     * @param chars 字符数组
     * @param usedLength 已使用的长度
     * @return
     */
    public static String replace(char[] chars, int usedLength) {

        if (null == chars || usedLength <= 0) {
            return null;
        }

        // 空格字符个数
        int spaceCount = 0;
        // 数组长度
        int oldLength = chars.length;

        for (int i = 0; i < usedLength; i++) {
            if (' ' == chars[i]) {
                spaceCount++;
            }
        }

        // 没有空格字符
        if (spaceCount == 0) {
            return String.valueOf(chars);
        }

        // 替换之后的长度=原来已使用长度+空格字符个数x2
        int targetLength = usedLength + spaceCount * 2;

        if (targetLength > oldLength) {
            return null;
        }

        usedLength--;
        targetLength--;

        // we are happy.
        while (usedLength >= 0 && targetLength > usedLength) {
            if (chars[usedLength] == ' ') {
                chars[targetLength--] = '0';
                chars[targetLength--] = '2';
                chars[targetLength--] = '%';
            }else{
                chars[targetLength--] = chars[usedLength];
            }
            --usedLength;
        }

        return String.valueOf(chars);
    }
}

测试类：

@Test
public void test() {

    char[] chars = new char[30];
    chars[0] = 'W';
    chars[1] = 'e';
    chars[2] = ' ';
    chars[3] = 'a';
    chars[4] = 'r';
    chars[5] = 'e';
    chars[6] = ' ';
    chars[7] = 'h';
    chars[8] = 'a';
    chars[9] = 'p';
    chars[10] = 'p';
    chars[11] = 'y';
    chars[12] = '.';

    System.out.println(ReplaceSpaceInString.replace(chars, 13));;
}

// We%20are%20happy.