Обрезка строки с <= 2 символами

Question

Предположим, вы получили строку ввода:

"my name is vikas"

Предложите алгоритм, чтобы изменить его на:

"name vikas"

Что означает удаление слов длиной <=2 или произнесение k символов, чтобы сделать его общим.

Answer 1

Я думаю, вы можете сделать это на месте за O(n) время. Перебирайте строку, сохраняя указатель на начало слова, которое вы обрабатываете. Если вы обнаружите, что длина слова больше k, вы перезаписываете начало строки этим словом. Вот код C (он предполагает, что каждое слово отделено точно в пространстве):

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);
}

Answer 2

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

(Scala)

Answer 3

Перебирать отдельные символы строки, сохраняя текущую позицию в строке и «текущее слово», накапливать все текущие слова длиной> = k, собирать строку из накопленных слов?

Этот алгоритм используетпереписать место и минимизировать количество копий между элементами:

    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));

Answer 4

split() на " " и пропустить if length() <= 2

Answer 5

Достаточно чего-то подобного (сложность времени оптимальна, я думаю):

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

А как насчет сложности пространства?Ну, это может работать в O (k) (мы не можем рассчитывать размер ввода и вывода, конечно), если вы думаете об этом.В .NET этого не будет, потому что Split создает реальный массив.Но вместо этого вы можете создавать итераторы.И если вы представите, что строка является просто итератором над символами, она станет алгоритмом O (1).