05.替换空格

OF5.替换空格 #

题目描述 #

题目地址

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

示例 1 #

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

限制 #

0 <= s 的长度 <= 10000

题解 #

思路 1 : 遍历添加 #

Python 和 Golang 的字符串都是不是修改的,不考虑内存的话可以开个数组方便操作。

算法流程:

  1. 初始化一个数组
  2. 循环遍历字符串
    1. 如果 v = 空格:后缀添加 %20
    2. 如果 v != 空格:后缀添加 v
  3. 数组转化为字符串

复杂度分析:

  • 时间复杂度$$O(N)$$**:**遍历字符串 s 一遍。
  • 空间复杂度$$O(N)$$ 额外创建字符数组,长度为 s 的长度的 3 倍

代码 #

{% tabs %} {% tab title=“Python3” %}

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

{% endtab %} {% endtabs %}

思路 2 : 原地置换 #

由于每次替换从 1 个字符变成 3 个字符,使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的 3 倍,这样可保证字符数组可以容纳所有替换后的字符。

算法流程:

  1. 获得 s 的长度 length
  2. 创建字符数组 ans,其长度为 length * 3
  3. 初始化 size 为 0,size 表示替换后的字符串的长度
  4. 从左到右遍历字符串 s
    1. 获得 s 的当前字符 c
    2. 如果字符 c 是空格,则令 array[size] = ‘%',array[size + 1] = ‘2’,array[size + 2] = ‘0’,并将 size 的值加 3
    3. 如果字符 c 不是空格,则令 array[size] = c,并将 size 的值加 1
  5. 遍历结束之后,size 的值等于替换后的字符串的长度,从 array 的前 size 个字符创建新字符串,并返回新字符串

复杂度分析:

  • 时间复杂度$$O(N)$$**:**遍历字符串 s 一遍。
  • 空间复杂度$$O(N)$$ 额外创建字符数组,长度为 s 的长度的 3 倍

代码 #

{% tabs %} {% tab title=“Go” %}

func replaceSpace(s string) string {
	result := make([]rune, len(s)*3)

	i := 0
	for _, v := range s {
		if v != ' ' {
			result[i] = v
			i++
		} else {
			result[i] = '%'
			result[i+1] = '2'
			result[i+2] = '0'
			i += 3
		}
	}
	return string(result)[:i]
}

{% endtab %} {% endtabs %}

#

总结 #

如果你同我一样热爱数据结构、算法、LeetCode,可以关注我 GitHub 上的 算法 题解: awesome-golang-algorithm