剑指offer—面试题5：字符串的替换

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

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

如果使用Swift 的系统API完成这个算法，其实很简单。

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

但这道算法题考察目的并不自此。首先我们要知道字符串在内存中的存储是线性表的格式，在内存是连续存放的。那么当我们将空格替换%20时，内存存放的数据是要挪动的。而算法所考察的就是我们如何高效的挪动这块内存。

如果我们从头开始遍历每次碰到空格将空格替换为 %20 时，需要将剩余的字符往后挪动两位，时间复杂度来说是 O(n^2)但如果反过来挪动，首先遍历一次计算出总共需要挪动的空间位置。给定两个指针p1、p2，p1 指向原始字符串的末尾，p2指向扩充后的字符串末尾。从后往前遍历，p1向前移动，每次移动字符从p1挪动到p2.碰到空格时 p1向前挪动，p2插入 %20 往前挪动三格。以此类推，直到p1、p2指针指向同一位置。