《劍指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)。