請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把字符串 s 中的每個(gè)空格替換成"%20"。
示例：

輸入：s = "We are happy."
輸出："We%20are%20happy."

如果使用Swift 的系統(tǒng)API完成這個(gè)算法，其實(shí)很簡(jiǎn)單。

    func replaceSpace(_ s: String) -> String {
        return s.replacingOccurrences(of: " ", with: "%20")
    }

但這道算法題考察目的并不自此。首先我們要知道字符串在內(nèi)存中的存儲(chǔ)是線性表的格式，在內(nèi)存是連續(xù)存放的。那么當(dāng)我們將空格替換%20時(shí)，內(nèi)存存放的數(shù)據(jù)是要挪動(dòng)的。而算法所考察的就是我們?nèi)绾胃咝У呐矂?dòng)這塊內(nèi)存。

如果我們從頭開始遍歷每次碰到空格將空格替換為 %20 時(shí)，需要將剩余的字符往后挪動(dòng)兩位，時(shí)間復(fù)雜度來說是 O(n^2)但如果反過來挪動(dòng)，首先遍歷一次計(jì)算出總共需要挪動(dòng)的空間位置。給定兩個(gè)指針p1、p2，p1 指向原始字符串的末尾，p2指向擴(kuò)充后的字符串末尾。從后往前遍歷，p1向前移動(dòng)，每次移動(dòng)字符從p1挪動(dòng)到p2.碰到空格時(shí) p1向前挪動(dòng)，p2插入 %20 往前挪動(dòng)三格。以此類推，直到p1、p2指針指向同一位置。