Trimming a string with <= 2 characters

Suppose you are given an input string:

"my name is vikas"

Suggest an algorith开发者_高级运维m to modify it to:

"name vikas"

Which means remove words having length <=2 or say k characters, to make it generic.

I think you can do this in-place in O(n) time. Iterate over the string, keeping a pointer to begining the word you're processing. If you find that the length of the word is greater than k, you overwrite the begining of the string with this word. Here's a C code (it assumes that each word is separated by exacly on space):

void modify(char *s, int k){

    int n = strlen(s);
    int j = 0, cnt = 0, r = 0, prev = -1;
    s[n++] = ' ';  // Setinel to avoid special case
    for(int i=0; i<n; i++){
        if(s[i] == ' '){
            if (cnt > k){
                if(r > 0) s[r++] = ' ';
                while(j < i) s[r++] = s[j++];
            }       
            cnt = 0;
        }
        else {
            if (prev == ' ') j = i;
            cnt++;
        }
        prev = s[i];
    }
    s[r] = '\0';
}
int main(){

    char s[] = "my name is vikas";
    modify(s, 2);
    printf("%s\n", s);
}

 "a short sentence of words" split ' ' filter {_.length > 2} mkString " "

(Scala)

Iterate over individual characters of String keeping the current position in the string and the "current word", accumulate all current words with length >= k, reassemble String from accumulated words?

This algorithm uses in-place rewriting and minimizes the number of copies between elements:

    final int k = 2;

    char[] test = "     my name     is el   jenso    ".toCharArray();
    int l = test.length;
    int pos = 0;
    int cwPos = 0;
    int copyPos = 0;

    while (pos < l)
    {
        if (Character.isWhitespace(test[pos]))
        {
            int r = pos - cwPos;
            if (r - 1 < k)
            {
                copyPos -= r;
                cwPos = ++pos;
            }
            else
            {
                cwPos = ++pos;
                test[copyPos++] = ' ';
            }
        }   
        else
        {
            test[copyPos++] = test[pos++];
        }
    }

    System.out.println(new String(test, 0, copyPos));

split() by " " and omit if length() <= 2

Something like that will suffice (time complexity is optimal, I guess):

input
 .Split(' ')
 .Where(s => s.Length > k)
 .Aggregate(new StringBuilder(), (sb, s) => sb.Append(s))
 .ToString()

What about space complexity? Well, this can run in O(k) (we can't count size of input and output, of course), if you think about it. It won't in .NET, because Split makes actual array. But you can build iterators instead. And if you imagine the string is just iterator over characters, it will become O(1) algorithm.