Space Replacement

Question

• lintcode: (212) Space Replacement

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.

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.

题解

根据题意，给定的输入数组长度足够长，将空格替换为%20 后也不会溢出。通常的思维为从前向后遍历，遇到空格即将%20 插入到新数组中，这种方法在生成新数组时很直观，但要求原地替换时就不方便了，这时可联想到插入排序的做法——从后往前遍历，空格处标记下就好了。由于不知道新数组的长度，故首先需要遍历一次原数组，字符串类题中常用方法。

需要注意的是这个题并未说明多个空格如何处理，如果多个连续空格也当做一个空格时稍有不同。

python

class Solution:
    # @param {char[]} string: An array of Char
    # @param {int} length: The true length of the string
    # @return {int} The true length of new string
    def replaceBlank(self, string, length):
        if string is None:
            return length

        spaces = 0
        for c in string:
            if c == ' ':
                spaces += 1

        L = length + spaces * 2
        index = L - 1
        for i in range(length - 1, -1, -1):
            if string[i] == ' ':
                string[index] = '0'
                string[index - 1] = '2'
                string[index - 2] = '%'
                index -= 3
            else:
                string[index] = string[i]
                index -= 1
        return L

源码分析

先遍历一遍求得空格数，得到『新数组』的实际长度，从后往前遍历。

复杂度分析

遍历两次原数组，时间复杂度近似为 $$O(n)$$, 使用了r 作为标记，空间复杂度 $$O(1)$$.