编写一个程序来删除给定字符串中的空格

Question

我已经用o(n)时间复杂度和o(n)空间复杂度的方法解决了相关问题，如下所示；但受访者希望o(n)时间复杂度与恒定的空间复杂度。如何在空间复杂度不变的情况下解决这个问题？

public static StringBuilder removeWhiteSpaces (String str){

    if (str == null){
        throw new IllegalArgumentException();
    }

    StringBuilder result = new StringBuilder();

    for (int i = 0 ; i < str.length(); i++){
        if (str.charAt(i) != ' '){
        result.append(str.charAt(i));
        }
    }
    return result;  
}

Answer 1

我不熟悉Java，但我记得String是不可变的。当要剥离的字符串存储在String中时，您所要求的操作是不可能完成的。这是因为我们不能修改输入，我们需要内存来存储结果。

但是，如果您可以将字符串存储在可变内存(例如char[]或StringBuilder)中，则可以使用以下算法。保留两个索引r和w并将其初始化为0。使用r遍历字符串，为读取的每个字符递增该值。如果该字符不是空格，则将其写入w并递增。

完成后，丢弃字符串的最后一个r - w字符。

C语言示例：

void remove_whitespace(char* s) {
    char* r = s;
    char* w = s;

    while (*r) {
        if (!std::isspace(*r)) *w++ = *r;
        ++r;
    }

    *w = 0;
}

Answer 2

在Java中，有两个好方法可以提高你的答案：

1)除了‘’之外，还有其他空格字符，您必须检查所有空格字符。使用Character.isWhitespace()或(如果你和我一样老)使用<=‘’。

2)您应该推迟生成StringBuilder，直到您实际看到一个空格字符。如果最后没有返回，只需返回原始字符串即可。

在Java中，大多数人会使用正则表达式搜索和替换来完成这项工作，但是如果您必须为此编写一个实用函数，最好是这样做(在这些改进之后)，因为这样会更高效。

如果面试官随后要求您提供常量空格，那么最好的回答是解释字符串在Java语言中是不可变的，因此您必须对接受StringBuilder参数的方法进行重载，然后该方法将被修改。在C++和C(orlp的答案)等其他流行语言中也有这样做的方法，但它们都等同于采用可变的StringBuilder，因此不需要切换语言。

Answer 3

面试中的问题是“来自给定的字符串”(字面意思是你必须使用String str作为输入)，或者你只是假设你必须使用String对象而不是char[]或StringBuilder。

对于String，它就不能工作了。一旦你使用了像str.toCharArray()这样的东西，你就会分配至少与str相同长度的新内存。而且您不能修改str中的字符，正如前面多次提到的那样。