《剑指offer》刷题系列——（四）替换空格

题目

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。例如：

输入：s = “We are happy.”

输出：“We%20are%20happy.”

思路

将一个空格字符替换成%、2、0三个字符，字符串会变长。第一种解决方案是在原来的字符串上进行替换，这样有可能覆盖修改该字符串后面的内容；另一种解决方案是创建新的字符串，并在新的字符串上进行替换，那么我们可以自己分配足够多的内存。这里我们采用第一种。

最直观的做法是从头到尾扫描字符串，遇到空格就替换成，把一个字符替换成三个字符，但是这样必须把空格后面的每一个字符都后移两位，这种方法的时间复杂度达到了O(n*n).

为了减少移动次数，我们采用从后往前的替换方式。

首先遍历一遍字符串，统计字符串中空格总数，然后计算替换之后的字符串的总长度。每替换一个字符空格，长度增加2，因此替换之后的字符串的总长度为原来的长度加上空格数乘以2。

然后从字符串的末尾开始复制和替换。准备两个指针P1和P2，P1指向原来字符串的末尾，P2指向替换后字符串的末尾。接下来开始从后向前遍历。

（1）如果P1指向的字符不是空格，就将其复制到P2指向的位置，P1和P2均向前移动1格；

（2）如果P1指向的字符是空格，就在P2之前插入三个字符%、2、0，P1向前移动1格，P2向前移动3格；

直到P1和P2指向同一个位置，表明所有空格都替换完毕，循环结束。

实例分析

测试用例

1、输入的字符串中包含空格（空格位于字符串的最前面；空格位于字符串的最后面；空格位于字符串的中间；字符串中有连续多个空格）。

2、输入的字符串中没有空格。

3、特殊输入测试（空字符串）。

解法一

直接用replace()函数。

class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(' ','%20')
           

解法二

按照思路中双指针的解法来做。这里涉及到很多python字符串的操作。相关知识点参考链接：Python 字符串操作

class Solution:
    def replaceSpace(self, s: str) -> str:
        
        OldLength = len(s)
        if OldLength < 1:
            return ""

        blankNum = 0
        for i in s:
            if i == ' ':
                blankNum += 1
        NewLength = OldLength + blankNum * 2

        for i in range(OldLength, NewLength):
            s += ' '

        index1 = OldLength-1
        index2 = NewLength-1

        while index1 < index2 and index1 >= 0:
            if s[index1] == ' ':
                s = s[:index2] + '0' + s[index2 + 1:NewLength]
                index2 -= 1
                s = s[:index2] + '2' + s[index2 + 1:NewLength]
                index2 -= 1
                s = s[:index2] + '%' + s[index2 + 1:NewLength]
                index2 -= 1
                index1 -= 1
            else:
                ch = s[index1]
                s = s[:index2] + ch + s[index2 + 1:NewLength]
                index1 -= 1
                index2 -= 1
        return s
           

复杂度分析

在上面的思路中可以看出，字符串中每一个字符都只复制移动了一次，因此时间复杂度为O(n)。