题目描述

[牛客网]

05. 替换空格

请实现一个函数,将一个字符串中的每个空格替换成 %20。例如,当字符串为 We Are Happy,则经过替换之后的字符串为 We%20Are%20Happy

解法 1:自带 replace

Python 其实就自带了 replace 方法。

实现与结果如下:

1
2
3
class Solution:
    def replaceSpace(self, s):
        return s.replace(' ', '%20')
  • 运行时间:33ms
  • 占用内存:5752k

解法 2:split 再 join

Python 还自带了 splitjoin 方法。

实现与结果如下:

1
2
3
class Solution:
    def replaceSpace(self, s):
        return '%20'.join(s.split(' '))
  • 运行时间:29ms
  • 占用内存:5752k

解法 3:遍历自行替换

这里我们假设按照 C 语言那种保存字符串的方式(Python 中字符串是不可变对象),然后我们从该字符串中替换所有的空格。如果我们从头到尾顺序替换,那么每次替换都要将后面所有的字符往后挪(因为长度为 1 的空格变成了长度为 3 的 %20),这样的复杂度巨大,为 $O(n^2)$。因此我们考虑先计算总共有多少个空格,然后计算好每个字符应该移动的距离,更妙的是,我们可以从尾到头来进行遍历移动

以题目中的 We Are Happy 为例,大致步骤如下:

  1. 先遍历一遍字符串,数一下空格的数量为 2,所以最多往后移动 4 位;
  2. 从尾到头遍历;
  3. 遇到空格之前,每个字符都后移 4 位;当遇到空格时,将空格替换为 %20,此后剩余的空格数量为 1,即字符最多后移 2位;
  4. 继续遍历,执行第 3 步操作,直到剩余空格数量为 1。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要遍历一遍数空格,和遍历一遍移动字符;
  • 空间复杂度为 $O(1)$,不需要额外空间。

代码略。