请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例 1： 输入：s = “We are happy.” 输出：“We%20are%20happy.” 限制： 0 str: counter = s.count(' ') res = list(s) # 每碰到一个空格就多拓展两个格子，1 + 2 = 3个位置存’%20‘ res.extend([' '] * counter * 2) # 原始字符串的末尾，拓展后的末尾 left, right = len(s) - 1, len(res) - 1 while left >= 0: if res[left] != ' ': res[right] = res[left] right -= 1 else: # [right - 2, right), 左闭右开 res[right - 2: right + 1] = '%20' right -= 3 left -= 1 return ''.join(res)
如果想把这道题目做到极致，就不要只用额外的辅助空间了！
首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。
!替换空格
有同学问了，为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
不用申请新数组。 从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
**笔者注：**从后向前遍历的这个方法很惊艳。第一次看到，双指针的每一个方法似乎都很惊艳。刚刚在思考有没有什么不额外空间的方法时一直的反应就是时间开销会到两次方。但是倒过来这个思路非常的有趣。
