替换空格

发表于

面试题5：替换空格

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

C++形式

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>

/*length 为字符数组的总容量。加判断体现鲁棒性*/
void ReplaceBlank(char str[], int length) {
    if(str == nullptr && length <= 0) {
        return;
    }
    int originalLength = 0;
    int numberOfBlank = 0;//空格数
    int i = 0;
    while(str[i] != '\0') {
        ++ originalLength;
        if (str[i] == ' ') {
            ++ numberOfBlank;
        }
        ++ i;
    }

    int newLength = originalLength + numberOfBlank * 2;
    if (newLength > length)//若超出数组长度限制
    {
        return;
    }
    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) {
        if (str[indexOfOriginal] == ' ') {
            str[indexOfNew --] = '0';
            str[indexOfNew --] = '2';
            str[indexOfNew --] = '%';
        }else {
            str[indexOfNew --] = str[indexOfOriginal];
        }
        -- indexOfOriginal;
    }
}

void Test(char* testName, char str[], int length, char expected[]) {
    if (testName != nullptr)
    printf("%s begins", testName);
    
    ReplaceBlank(str, length);
    if (expected == nullptr && str == nullptr) {
        printf("passed.\n");
    }else if (expected == nullptr && str != nullptr) {
        printf("failed.\n");
    }else if (strcmp(str, expected) == 0) {
        printf("passed.\n");
    }else {
        printf("failed.\n");
    }
}

void Test1() {
    const int length = 100;
    char str[length] = "hello world";
    Test("Test1",str,length,"hello%20world");
}

int main(int argc, char* argv[]) {

Test1();

return 0;
}

思路

先遍历统计出空格总数，从而得出替换之后的字符串总长度。
用两个指针从后往前把字符串中的空格替换成”%20”。

时间复杂度

所有的字符只移动一次，该算法时间复杂度为O(n)。