【每日一题】03.替换空格

题目:

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

分析:

方案一、灵活使用php相关函数

其中替换函数有str_replace ($search, $replace, $subject, &$count = null)

和strstr($haystack, $needle, $before_needle = null)

但是strstr替换成不能被替换为空，也就是末位那个参数不能是空字符串

所以只能选择str_replace

方案二、从左向右扫描字符串替换

一个字符替换为三个

每遇到一个空格，空格后面所有字符向右移动两个位置字符串长度为n，

对每个空格而言，需要移动后面O(n)个字符算法的时间复杂度为O(n^2)

方案三、从右到左扫描字符串替换

统计空格数，字符串长度增加 空格数 * 2

维持两个指针p1, p2

p1指向原字符串长度末尾， p2指向新字符串长度末尾

当p1遇到空格时， p2 向前移动并替换字符为 '0' '2' '%'

把p1指针指向的字符拷贝到p2指针指向的字符

所有字符都只移动一次，时间复杂度为O(n)

代码示例

关于 喝醉的清茶