题解 | #替换空格#

思路

看到题的第一反应就是顺序遍历这个字符串，遇到空格就替换。

不过《剑指offer》这本书里详细的阐述了这种算法的时间复杂度是O(n^2)，因为对一个长度为n的字符串来说，每一次替换其实就是要把空格之后的部分挪动两次。

这种代码很好写。

Java版本

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    public String replaceSpace(String s) {
        // write code here
        int len = s.length();
        char[] chars = s.toCharArray();
        List<String> dest = new ArrayList<>();
        for (char str : chars) {
            if (str == ' ') {
                dest.add("%20");
            } else {
                dest.add(String.valueOf(str));
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        dest.forEach(stringBuilder::append);
        return stringBuilder.toString();
    }
}

执行时间115ms。

另外书中提到了一种时间复杂度为O(n)的解法，看起来需要遍历两次字符串，其实效果更好。主要的思路就是首先计算出原字符串里有多少个空格，然后新建一个字符串，这个字符串的长度是原字符串长度加上两倍的空格数量。

然后遍历原字符串，将每一个字符复制到新字符串里，逢空格进行特殊处理即可。

Java版本代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    public String replaceSpace(String s) {
        // write code here
        int len = s.length();
        char[] originalString = s.toCharArray();
        int numberOfBlanks = 0;
        for (char c : originalString) {
            if (c == ' ') {
                numberOfBlanks += 1;
            }
        }
        int newStringLen = len + numberOfBlanks * 2;
        char[] newString = new char[newStringLen];
        for (int i = len - 1, j = newStringLen - 1; i >= 0; i--) {
            if (originalString[i] == ' ') {
                newString[j--] = '0';
                newString[j--] = '2';
                newString[j--] = '%';
            } else {
                newString[j--] = originalString[i];
            }
        }
        return String.valueOf(newString);
    }
}

这段代码的执行时间就缩短到了21ms，效果非常好。

C语言的效率更高，只需要5ms：

C语言版本

#include <stdio.h>
#include <malloc.h>
#include <string.h>


char* replaceSpace(char* s) {
    // write code here
    int originalLength = strlen(s), numberOfBlanks = 0;

    // 第一次遍历得到数组长度和空格长度
    for (int i = 0; i < originalLength; i++)
    {
        if (s[i] == ' ')
        {
            numberOfBlanks += 1;
        }
    }
    // 替换后的字符串长度
    int newStringLength = originalLength + numberOfBlanks * 2;
    // 分配一段内存给新的字符串用
    char *newString = (char *)malloc(newStringLength + 1);
    for (int i = originalLength - 1, j = newStringLength - 1; i >= 0; i--)
    {
        if (s[i] == ' ')
        {
            newString[j--] = '0';
            newString[j--] = '2';
            newString[j--] = '%';
        }
        else
        {
            newString[j--] = s[i];
        }
    }
    newString[newStringLength + 1] = '\0';
    return newString;
}