题目难度: 简单
原题链接
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
URL 化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用 Java 实现的话，请使用字符数组实现，以便直接在数组上操作。）
示例 1:
输入："Mr John Smith ", 13 输出：“Mr%20John%20Smith”
示例 2:
输入：" “, 5 输出：”%20%20%20%20%20"
提示：
字符串长度在[0, 500000]范围内。
题目思考
如何做到原地修改？
解决方案
思路
不难想到利用各种语言的 replace 或 split/join 来实现；或者新建一个字符串，遇到空格就追加%20。但这些做法都没有利用题目中的真实长度和字符数组，不是原地操作题目中说明了字符数组有足够空间存放新字符，所以我们可以先计算得出新字符串的总长度，然后维护一个当前下标，从右向左遍历，这样就保证了是原地操作，且不会覆盖到之前存在且尚未处理的字符
复杂度
时间复杂度 O(N): 需要遍历字符串一遍空间复杂度 O(1): 除了字符数组外只使用了几个变量
代码
class Solution:
def replaceSpaces(self
, S
: str, length
: int) -> str:
newlen
= length
blank
= 0
for c
in S
[:length
]:
if c
== ' ':
blank
+= 1
newlen
+= blank
* 2
res
= [''] * newlen
i
= newlen
- 1
for c
in S
[:length
][::-1]:
if c
== ' ':
res
[i
] = '0'
res
[i
- 1] = '2'
res
[i
- 2] = '%'
i
-= 3
else:
res
[i
] = c
i
-= 1
return ''.join
(res
)
大家可以在下面这些地方找到我~😊
我的知乎专栏
我的头条号
我的
我的 Leetcode
我的牛客网博客
我的公众号: 算法精选, 欢迎大家扫码关注~😊
