of005.md

description
剑指 Offer 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