code4offer-2 替换空格

替换空格

问题描述

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

分析

乍一看不就一个replace解决问题，的确这样是能AC的

如下面这个C#版的，一行就能解决

1
2
3
4
public string replaceSpace(string str)
{
    return str.Replace(" ", "%20");
}

如果不用自带的replace偷懒，有两种思路：

  1. 创建新的字符串
  2. 原地replace

创建新字符串

这种方法比较简单，空间换时间，时间复杂度$O(n)$，空间复杂度$O(n)$

1
2
3
4
5
6
7
8
9
10
public String replaceSpace(StringBuffer str) {
    String result = "";
    int len = str.length();
    for (int i = 0; i < len; i++) {
        if (str.charAt(i) == ' ') { result += "%20";}
        else {result += str.charAt(i);}
    }

    return result;
}

原地replace

以C++为例，原地replace要考虑到String的储存方式，是存在一块连续的内存里，空格可能出现在字符串的中间位置，要替换成%20需要将空格后的元素向后移动腾出位置

  1. 统计空格的数量emptyCount（一次for循环）
  2. 计算元素向后移动的偏移量offset

每多一个空格，元素就要多向后移动2位，当一个空格被%20填充后，需要后移的位数就减少2

offset = (emptyCount - tmpCount) * 2

' '和%20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void replaceSpace(char *str,int length) {
    int emptyCount = 0, tmpCount = 0;
    for(int i = 0; i < length; ++i) {
        if (str[i] == ' ') {
            ++emptyCount;
        }
    }

    for (int j = length - 1; j >= 0; --j) {
        if (str[j] == ' ') {
            str[j+(emptyCount - tmpCount)*2] = '0';
            str[j+(emptyCount - tmpCount)*2-1] = '2';
            str[j+(emptyCount - tmpCount)*2-2] = '%';
            ++tmpCount;
            continue;
        }
        str[j+(emptyCount - tmpCount) * 2] = str[j];
    }
}