Анализ сложности: удаление последовательных (3+) дубликатов из строки - PullRequest
Новая
       31

Анализ сложности: удаление последовательных (3+) дубликатов из строки

0 голосов
/ 28 мая 2019

Я написал решение для удаления 3 (давайте назовем это k) или более последовательных одинаковых символов из строки.например.

in: daabbcccbbaad out: dd
in: aaabbb out: 
in: aaabbbc out: c

код: 

void removeDup(string& s, int start) {
    if (s.length() < 3) {
        return;
    }

    if (start > s.length() - 2) return;

    int count = 1;
    char c = s[start];

    int i = start + 1;

    while (i < s.length() && s[i] == c) {
        ++count, ++i;
    }

    if (count >= 3) {
        start = i - count - 2;
        if (start < 0) start = 0;
        s.erase(i - count, count);
    } else {
        start = i;
    }

    return removeDup(s, start);
}

Для каждого совпадения start указатель будет перемещаться на 2 шага позади.Также размер проблемы уменьшается без совпадения символов.

Я хочу понять, как сделать анализ сложности для этого.Также для любого k (скажем, k=n/2) как изменится сложность.

ps: если у вас есть лучшее решение с постоянным пространством, пожалуйста, напишите.

...