目录

• 1、题目描述：
• 2、方法一：使用额外空间
• • 思路：
  • 代码：
• 3、方法二：暴力法
• • 思路：
  • 代码：
• 4、方法三：双指针
• • 思路：
  • 代码：

1、题目描述：

注意：由于Python的字符串是不可变类型，因此我在下面转换成list做，不计入空间复杂度哦！

2、方法一：使用额外空间

思路：

这个方法最简单，即遍历原始的数组，遇到了空格，就在新的数组中添加’%’，‘2’，'0’这三个字符。下面我直接贴一个没有转换为list的代码（基本一样的）：

代码：

class Solution:def replaceSpace(self, s: str) -> str:ans = ""for each in s:if each == " ":ans += "%20"continueans += eachreturn ans

3、方法二：暴力法

思路：

面试官要求不能使用额外空间呢？这个题又怎么做？

最朴素的思想是：遍历原始字符串（python这里我转换为list），每次遇到空格后，将空格后面的所有字符都后移动两位，然后把’%’，‘2’，'0’这三个字符添加在空格以及后移空出来的两位置。每次遇到空格都要移动后面所有的字符，时间复杂度为$O(n^2)$，贴一个代码：

代码：

class Solution:def replaceSpace(self, s: str) -> str:s = [ss for ss in s] # 转换为listlength = len(s)i = 0while i < len(s):if s[i] == ' ': # 向后移两位end1, end2 = s[-1], s[-2] # 由于Python没有预先开辟空间的说法，这里只能保存最后两个s.append(end2)s.append(end1)for j in range(len(s)-5, i, -1):s[j+2] = s[j]s[i], s[i+1], s[i+2] = '%', '2', '0'i += 2i += 1return ''.join(s)

4、方法三：双指针

思路：

如果不用额外的辅助空间，怎么做？

首先扩充数组的大小，即扩充到每个空格替换成"%20"之后的大小。然后从后向前替换空格，也就是双指针法，过程如下：$i$指向新长度的末尾，$j$指向旧长度的末尾。

图来源于代码随想录！！

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

1、不用申请新数组。
2、从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。

代码：

class Solution:def replaceSpace(self, s: str) -> str:s_list = [ss for ss in s] # 转换为list,分析的时候不计入空间复杂度# 1.统计s_list中空格的个数nums = 0for i in range(len(s_list)):if s_list[i] == ' ': nums += 1# 2.扩充s_list为nums的2倍,这里用空格填充for _ in range(2*nums):s_list.append(' ')# 3.使用两个指针替换空格i, j = len(s_list)-1, len(s)-1 # 分别指向新旧数组的末尾while j >= 0:if s_list[j] == ' ': # 为空格,则把i向前移动三位，并把这三位赋值为'%', '2', '0's_list[i-2], s_list[i-1], s_list[i] = '%', '2', '0'i -= 3else: # 不为空格，把j位置的字符赋值给i位置,并把i向前移动一位s_list[i] = s_list[j]i -= 1j -= 1return ''.join(s_list)