题目描述

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

示例

示例 1：

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

解答方法

方法一：

思路

• 初始化一个 list ，记为 res ；
• 遍历列表 s 中的每个字符 c ：
  • 当 c 为空格时：向 res 后添加字符串 "%20"；
  • 当 c 不为空格时：向 res 后添加字符 c ；
• 将列表 res 转化为字符串并返回。

代码

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for i in s:
            if i == ' ':
                res.append('%20')
            else:
                res.append(i)
        return ''.join(res)

时间复杂度

O(N)： 遍历使用 O(N) ，每轮添加（修改）字符操作使用 O(1) ；

空间复杂度

O(N) ： Python 新建的 list 使用了线性大小的额外空间。

方法二：双指针法

思路

• 首先遍历一次字符串s来统计空格个数n
• 额外开辟出2*n个空间
• 将开辟出的空间链接到原字符串的后面,新的字符串s.设置两个指针p1和p2,初始时p1指向原字符串s的末尾,p2指向s_new的末尾
• p1指针向前移动,
  • 当p1指向的字符不是空格时,将p1指向的字符复制到p2指向的位置,并都向前移动一位
  • 当p1指向的字符是空格时,p1向前移动一格,这时应该插入%20,所以p2向前移动三格,并在这三格中插入%,2,0

代码

class Solution:
    def replaceSpace(self, s: str) -> str:
        if not s:
            return ''
        s = list(s)
        #获取空格数目
        blank_num = 0
        for i in s:
            if i == ' ':
                blank_num+=1
        pre_len= len(s)
        #扩展源字符串中长度
        s.extend([None for i in range(2*blank_num)])
        #双指针从后往前扫描
        p1 = pre_len - 1
        p2 = len(s) - 1
        while p1 >=0 and p1!= p2:
            if s[p1] == ' ':
                s[p2-2] = '%'
                s[p2-1] = '2'
                s[p2] = '0'
                p2 -= 3
            else:
                s[p2] = s[p1]
                p2 -= 1
            p1 -=1
        return ''.join(s)