剑指offer-替换空格

题目描述

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

分析

这套题本质就是一个字符串替换啊!
所以上来直接用Python的replace方法,还给AC过了.

后来切回到C++,想了一下,那我就构造一个新的字符串吧,最大长度就是原先字符串的3倍,然后依次复制过去,遇到空格就特殊处理一下.这样是用空间换时间.

最后能不能在线处理呢,是可以的.也就是在原先的字符串上处理,由于如果从前向后处理,那么将空格换成%20,就要将后面的字符均向后移动,这样显然就是效率低了.

所以要从后向前处理,先统计空格的数量,然后计算出替换以后字符串的长度,然后定义两个指针,一个处于新字符串的最后,一个处于原来字符串的最后,这样从后向前依次替换就行!这样效率是最高的,空间也是最优的.

这三个方案的结果统计如下,以此为在线处理、新建字符串、replace API.

代码

  • Python replace办法

    1
    2
    3
    4
    5
    # -*- coding:utf-8 -*-
    class Solution:
    # s 源字符串
    def replaceSpace(self, s):
    return s.replace(' ','%20')
  • 新建一个字符串

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
    void replaceSpace(char *str,int length) {
    if(str==NULL && length<=0){
    return;
    }
    char new_str[length*3];
    int j = 0;
    for(int i=0;i<length;i++){
    if(str[i]==' '){
    new_str[j++] = '%';
    new_str[j++] = '2';
    new_str[j++] = '0';
    }else{
    new_str[j++] = str[i];
    }
    }
    strcpy(str, new_str);
    }
    };

注意最后用strcpy函数覆盖原先的字符串.

  • 在线处理
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
    void replaceSpace(char *str,int length) {
    if(str==NULL && length<=0){
    return;
    }
    int space_count = 0;
    for(int i=0;i<length;i++){
    if(str[i]==' '){
    space_count ++;
    }
    }
    int new_length = length + 2*space_count;
    int p2 = new_length-1;
    int p1 = length-1;
    while(p1>=0){
    if(str[p1]==' '){
    str[p2--]='0';
    str[p2--]='2';
    str[p2--]='%';
    p1--;
    }else{
    str[p2--] = str[p1--];
    }
    }
    }
    };