标签: 字符串
难度: Easy
URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
示例 1：
输入："Mr John Smith ", 13 输出："Mr%20John%20Smith"
示例 2：
输入：" ", 5 输出："%20%20%20%20%20"
提示：
- 字符串长度在 [0, 500000] 范围内。
Submission
运行时间: 32 ms
内存: 22.3 MB
class Solution:
def replaceSpaces(self, S: str, length: int) -> str:
return S[:length].replace(' ', '%20')
Explain
该题解采用了直接操作字符串的方法。首先，通过截取输入字符串直到给定的“真实”长度，以去除尾部可能的空白或额外空间。然后，使用字符串的replace方法，将截取后的字符串中的所有空格字符替换为'%20'。这种方法简洁且直接，便于理解和实现。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def replaceSpaces(self, S: str, length: int) -> str:
# 截取到指定的'真实'长度，去除尾部多余空间
trimmed_string = S[:length]
# 将截取后的字符串中的空格替换为'%20'
return trimmed_string.replace(' ', '%20')
Explore
在输入字符串的'真实'长度小于字符串总长度且字符串尾部包含空格的情况下，截取后仍会有尾部空白。这是因为'真实'长度仅指定到尾部之前的某个字符，不包括尾部空格。例如，字符串 'Mr John Smith ' 的真实长度为13，意味着除了尾部的空格外，其余部分为有效内容。
执行`replace`方法之前进行字符串截取的原因是为了去除尾部的多余空间或空格，这样可以确保替换过程只发生在需要处理的字符串范围内，提高效率和准确性。虽然可以在不截取的情况下直接替换所有空格为`%20`，然后再按真实长度截取，但这样会导致在原本应当被忽略的尾部空白区域也进行不必要的替换操作，增加处理时间和资源消耗。
该算法的时间复杂度主要是O(n)，其中n是字符串的真实长度。字符串截取操作是O(n)复杂度，因为它涉及从原始字符串中复制出新的子字符串。替换操作同样是O(n)复杂度，因为它可能需要遍历整个截取后的字符串并替换每个空格。总体来说，这两个操作都直接涉及到字符串长度，因此是线性复杂度。尽管如此，截取和替换是必要的步骤以保证解决方案的正确性和效率，因而它们是对效率的合理影响。