剑指offer 面试题4：替换空格

题目：
请实现一个函数，把字符串中的每个空格替换成"20%"。例如输入"We are happy"，则输出"We%20are%20happy"。

假设原字符串后有足够的内存空间，不会出现内存踩踏。

解法：
排除另开辟空间的方法。
常规解法是，从头到尾遍历，遇到空格时，把空格后面的字符串依次后移。但该种方法会导致某些字符重复移动。
更合适的方法是，先计算出原字符串中有多少空格，然后从尾到头遍历，因为一开始就知道被移动字符的最终位置，因此可以避免字符的重复移动。时间复杂度O(n)

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容