Interview Question : Trim multiple consecutive spaces from a string

This is an interview question Looking for best optimal solution to trim multiple spaces from a string. This operation should be in-place operation.

input  = "I    Like    StackOverf开发者_运维知识库low a      lot"
output = "I Like StackOverflow a lot"

String functions are not allowed, as this is an interview question. Looking for an algorithmic solution of the problem.

Does using <algorithm> qualify as "algorithmic solution"?

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
struct BothAre
{
    char c;
    BothAre(char r) : c(r) {}
    bool operator()(char l, char r) const
    {
            return r == c && l == c;
    }
};
int main()
{
    std::string str = "I    Like    StackOverflow a      lot";
    std::string::iterator i = unique(str.begin(), str.end(), BothAre(' '));
    std::copy(str.begin(), i, std::ostream_iterator<char>(std::cout, ""));
    std::cout << '\n';
}

test run: https://ideone.com/ITqxB

A c++0x - solution using a lambda instead of a regular function object. Compare to Cubbi's solution.

#include <string>
#include <algorithm>

int main()
{
    std::string str = "I    Like    StackOverflow a      lot";

    str.erase(std::unique(str.begin(), str.end(),
      [](char a, char b) { return a == ' ' && b == ' '; } ), str.end() );  
}

Keep two indices: The next available spot to put a letter in (say, i), and the current index you're examining (say, j).

Just loop over all the characters with j, and whenever you see a letter, copy it to index i, then increment i. If you see a space that was not preceded by a space, also copy the space.

I think this would work in-place...

I'd just go with this:

int main(int argc, char* argv[])
{
    char *f, *b, arr[] = "  This        is    a test.                ";
    f = b = arr;

    if (f) do
    {
        while(*f == ' ' && *(f+1) == ' ') f++;
    } while (*b++ = *f++);

    printf("%s", arr);

    return 0;
}

I'd propose a little state machine (just a simple switch statement). Because if the interviewer is anything like me, the first enhancement they'll ask you to do is to fully trim any leading or trailing spaces, so that:

"    leading and    trailing    "

gets transformed to:

"leading and trailing"

instead of:

" leading and trailing "

This is a really simple modification to a state-machine design, and to me it seems easier to understand the state-machine logic in general over a 'straight-forward' coded loop, even if it takes a few more lines of code than a straight-forward loop.

And if you argue that the modifications to the straight forward loop wouldn't be too bad (which can be reasonably argued), then I (as the interviewer) would throw in that I also want leading zeros from numbers to be be trimmed.

On the other hand, a lot of interviewers might actually dislike a state-machine solution as being 'non-optimal'. I guess it depends on what you're trying to optimize.

Here it is using only stdio:

#include <stdio.h>

int main(void){
    char str[] = "I    Like    StackOverflow a      lot";
    int i, j = 0, lastSpace = 0;
    for(i = 0;str[i]; i++){
        if(!lastSpace || str[i] != ' '){
            str[j] = str[i];
            j++;
        }
        lastSpace = (str[i] == ' ');
    }
    str[j] = 0;
    puts(str);
    return 0;
}

Trimming multiple spaces also means a space should always be followed by a non space character.

int pack = 0;
char str[] = "I    Like    StackOverflow a      lot";
for (int iter = 1; iter < strlen(str); iter++)
{
    if (str[pack] == ' ' && str[iter] == ' ')
        continue;
    str[++pack] = str[iter];
}
str[++pack] = NULL;

int j = 0;
int k=0;
char str[] = "I    Like    StackOverflow a      lot"; 
int length = strlen(str);
char str2[38];
for (int i = 0; i < length; i++) 
{ 
    if (str[i] == ' ' && str[i+1] == ' ') 
     continue; 
    str2[j] = str[i];
    j++;
} 

str2[j] =NULL;

cout<<str2;

void trimspaces(char * str){
    int i = 0;
    while(str[i]!='\0'){
        if(str[i]==' '){
            for(int j = i + 1; j<strlen(str);j++){
                if(str[j]!=' '){
                    memmove(str + i + 1, str + j, strlen(str)-j+1);
                    break;
                }
            }
        }
        i++;
    }
}

Functional variant in Haskell:

import Data.List (intercalate)

trimSpaces :: String -> String
trimSpaces =  intercalate " " . words

The algorithm the next:

1. breaks a string up into a list of words, which were delimited by white space
2. concatenate the list inserting one space between each element in list

This is a very simple implementation of removing extra whitespaces.

#include <iostream>
std::string trimExtraWhiteSpaces(std::string &str);
int main(){
    std::string str = "  Apple    is a     fruit  and I like     it   .  ";
    str = trimExtraWhiteSpaces(str);
    std::cout<<str;
}
std::string trimExtraWhiteSpaces(std::string &str){
    std::string s;
    bool first = true;
    bool space = false;
    std::string::iterator iter;
    for(iter = str.begin(); iter != str.end(); ++iter){
        if(*iter == ' '){
            if(first == false){
                space = true;
            }
        }else{
            if(*iter != ',' && *iter != '.'){
                if(space){
                    s.push_back(' ');
                }
            }
            s.push_back(*iter);
            space = false;
            first = false;
        }
    }
    return s;
}

std::string tripString(std::string str) {
    std::string result = "";
    unsigned previous = 0;
    if (str[0] != ' ')
        result += str[0];
    for (unsigned i = 1; i < str.length()-1; i++) {
        if (str[i] == ' ' && str[previous] != ' ')
            result += ' ';
        else if (str[i] != ' ')
            result += str[i];
        previous++;
    }
    if (str[str.length()-1] != ' ')
        result += str[str.length()-1];
    return result;
}

This may be an implementation of the accepted idea.