[LintCode] 212 Space Replacement 解题报告

Description
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".


Challenge
Do it in-place.


思路
先统计一下空格数，算出字符串要多长。
从这个长度从后往前一个一个插入。


Code

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 end = length;
        for (int i = 0; i < length; i++) {
            if (string[i] == ' ') {
                end += 2;
            }
        }
        int result = end;
        end--;
        for (int i = length - 1; i >= 0; i--) {
            if (string[i] != ' ') {
                string[end--] = string[i];
            }
            else {
                string[end--] = '0';
                string[end--] = '2';
                string[end--] = '%';
            }
        }
        return result;
    }
}