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.

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.

 

思路:

1、算出填充完空格后数组的实际长度为多少,一个空格相当于要多占2个字符,所有实际长度=原内容长度+空格数*2

2、用2个指针,一个指向填充完空格后数组的末尾(指针1),一个指向当前数组内容的末尾(指针2)。从数组后向前遍历,如果不是空格,则直接把当前位置的内容放到指针1对应的位置。如果为空格则将指针1向前移2个位置,写入%20。

3、一定要从后向前遍历,这样可以减少挪动数组元素的次数。

 

发表评论