文章目录

1. 题目2. 解题思路2.1 思路12.2 思路2 3. 代码实现3.1 解法一3.2 解法二 4. 总结5. 参考文献

1. 题目

请实现一个函数，将一个字符串中的空格替换成“%20”。 例如，输入"We Are Happy."则输出We%20Are%20Happy。

其实在URL中如果有特殊字符（如：空格、双引号、’#’等），可能导致服务器无法正确识别浏览器传递的参数，因此需要将这些特殊字符先转换之后再传递给服务器。python2中的urllib.urlencode()就是将查询字符串（dict）转换后在传递给服务器的，或者使用urllib.quote直接将将字符串转换。

在python3中需要使用urllib.parse.urlparse()方法。

2. 解题思路

本题不使用新的字符串来接收替换之后的结果，而是原地修改。

解题的关键在于：

空格只占用一个字符，而"%20"占用了3个字符，因此将空格替换为"%20"的话，原空格之后的字符串中的字符都需要往后移动2个位置。如何尽可能少的移动原字符串的位置是降低时间复杂度的关键。

2.1 思路1

直接从前往后遍历，当遇到空格时，使用’%20’替换，并将此空格之后的所有字符都往后平移2格，循环下去。

时间复杂度O(n²)，空间复杂度S(1)。

2.2 思路2

先遍历一遍，计算出字符串中空格的数量，事先分派好替换之后的字符串的长度。

从后往前遍历，在事先就确定好字符串中字符的位置，不在移动多余的字符了。

时间复杂度O(n)，空间复杂度S(1)。

3. 代码实现

3.1 解法一

由于在python中的str类型是不可变对象，咱也无法在原地修改它，所在算法中咱使用list对象代替。在python咱也不能给list申请大小，都是python自己搞的，咱理解这个思路就好了。

思路1的代码实现：

class Solution: def __init__(self): pass def replace_blank(self, string): """替换空格 :param string :return None """ if not isinstance(string, list): raise TypeError('string must be list type!') for char in string: if char == ' ': char = '%20' return ''.join(string) if __name__ == '__main__': string = list('we are happy.') s = Solution() print(s.replace_blank(string))

3.2 解法二

将python中的list当作c中的str来用。

思路2的代码实现如下:

class Solution: def __init__(self): pass def replace_blank(self, string): """替换空格 :param string :return None """ if not isinstance(string, list): raise TypeError('string must be list type!') blank_count = 0 for i in string: if i == ' ': blank_count += 1 new_length = len(string) + 2 * blank_count new_string = [None for i in range(new_length)] # 相当于定义两个指针，一个指向原来字符串末尾，另一个指向新字符串的末尾。 index_old = len(string) - 1 index_new = len(new_string) - 1 while index_old >= 0 and index_new >= index_old: if string[index_old] == ' ': new_string[index_new] = '0' index_new -= 1 new_string[index_new] = '2' index_new -= 1 new_string[index_new] = '%' index_new -= 1 else: new_string[index_new] = string[index_old] index_new -= 1 index_old -= 1 print(new_string) return ''.join(new_string) if __name__ == '__main__': string = list('we are happy.') s = Solution() print(s.replace_blank(string))

4. 总结

从前往后替换字符串时，许多字符会重复移动，这就大大增加了时间复杂度。

当确定好最后的字符串长度之后，从后往前替换，就避免了元素的重复移动，所有字符串都最多移动一次，一步到位。

5. 参考文献

[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题