Problem

Write a method to replace all spaces in a string with %20. The string is given in a characters array, you can assume it has enough space for replacement and you are given the true length of the string.

You code should also return the new length of the string after replacement.

Example

Given "Mr John Smith", length = 13.

The string after replacement should be "Mr%20John%20Smith".

Note

If you are using Java or Python，please use characters array instead of string.

Challenge

Do it in-place.

Solution

It's a easy problem but you are required to do it in-place.
No StringBuilder.

public class Solution {
    public int replaceBlank(char[] str, int length) {
        if (length == 0) return 0;
        int len = length;
        //calculate the new length after all the replacements
        for (int i = 0; i < len; i++) {
            if (str[i] == ' ') {
                len += 2;
            }
        }
        int j = 1;
        //这里要注意：循环的是前length-1个元素，不是len-1
        for (int i = length - 1; i >= 0; i--) {
            //当前元素i--在for循环条件里前移，新位置的指针(len - j++)在if-else语句前移
            if (str[i] == ' ') {
                //序数从后向前 len-1 len-2 len-3
                str[len - j++] = '0';
                str[len - j++] = '2';
                str[len - j++] = '%';
            }
            //没有空格也要把当前位元素移到新的位置 
            else {
                str[len - j++] = str[i];
            }
        }
        return len;
    }
}