Space Replacement 212

Question

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.

Notice

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

Example

Given "Mr John Smith", length = 13.

The string after replacement should be "Mr%20John%20Smith", you need to change the string in-place and return the new length 17.

Challenge

Do it in-place.

Solution

这道题要求将“ ”替换成"%20"。

首先找到一共有多少个" "，将“ ”替换成"%20"，则每个空格比原来多2个字符，因此新的字符串长度为原字符串长度+2 * 空格数目。

然后从后往前遍历原数组，新数组也从后往前加入新元素。若遇到的字符是" "，则将"0","2","%"依次加入新数组（从后往前），若不是" "，则直接将遇到的字符加入新数组。在遇到最后一个" "之前一定不会出现新数组加入元素的左边界快于原数组的情况，直到最后一个" "两个的左边界才会重合。

代码如下：

public class Solution {
    /**
     * @param string: An array of Char
     * @param length: The true length of the string
     * @return: The true length of new string
     */
    public int replaceBlank(char[] string, int length) {
        // Write your code here
        int count = 0;
        for(int i = 0; i < length; i++){
            if(string[i] == ' '){
                count++;
            }
        }
        int newLen = length + 2 * count;

        int j = 1;
        for(int i = length - 1; i >= 0; i--){
            if(string[i] != ' '){
                string[newLen - j] = string[i];
                j++;
            }else{
                string[newLen - j] = '0';
                j++;
                string[newLen - j] = '2';
                j++;
                string[newLen - j] = '%';
                j++;
            }
        }

        return newLen;
    }
}