Задачи по алгоритмам: избавляемся от анаграмм

https://leetcode.com/problems/find-resultant-array-after-removing-anagrams/

Дан массив слов words. Слово содержит латинские буквы в нижнем регистре a-z. Проверить пары смежных слов и удалить , когда и - анаграммы.

Строки a и b - анаграммы, когда b получается из a перестановкой символов и наоборот.

a.length() == b.length() && a.sort() == b.sort()

Ищем анаграммы в массиве

Заметим, если a, b - анаграммы, b, c - анаграммы, то a, c - анаграммы. Математики называют такие отношения транзитивными.

Найдем группы смежных анаграмм и оставим в массиве первую строку каждой группы.

w3 и w6 - не анаграммы, когда w3 и w5 - анаграммы, а w5 и w6 - нет.

Предлагаю два способа:

• Ищем первую и последнюю анаграмму группы

  

• Ищем границы между группами - пары смежных "не анаграмм"

  

Напишу код первым способом, а позже испытаю второй.

Сэкономим память - пишем результат поверх исходного массива.

vector<string> removeAnagrams(vector<string>& words) {
    int write = 0;
    int begin = 0;
    int end = begin + 1;
    while (begin < words.size()) {
        while (end < words.size() && areAnagrams(words[begin], words[end])) {
            ++end;
        }
        std::swap(words[write++], words[begin]);
        begin = end;
        end = begin + 1;
    }
    words.resize(write);
    return words;
}

Цикл обходит группы анаграмм и пишет первую строку группы по указателю write.

Цикл выбирает первую строку каждой группы, пишет по указателю writeи переходит к следующей группе.

begin указывает на начало группы анаграмм. Вложенный цикл сдвигает end так, чтобы end - 1 указал последнюю анаграмму группы.

vector<string> words{"Hello"s, "World"s};
for (int i = 0; i < words.size(); ++i) {
    words[i] = std::move(words[i]);
}
for (const auto &w: words) {
    // пустые строки
    cout << w << endl;
}

Пишем функцию areAnagrams, что узнает анаграммы

C++ предлагает такие способы узнать анаграммы:

Посчитаем буквы с помощью массива

Латинский алфавит содержит 26 букв. Объявим массив размера 26 и посчитаем, сколько раз слово содержит каждую букву.

bool areAnagrams(const string &lhs, const string &rhs) {
    if (lhs.size() != rhs.size()) {
        return false;
    }

    vector<int> stat(26);
    for (char c: lhs) {
        ++stat[c - 'a'];
    }
    for (char c: rhs) {
        --stat[c - 'a'];
    }
    for (int num: stat) {
        if (0 != num) {
            return false;
        }
    }
    
    return true;
}

• Время: O(n)

• Память: 26 * sizeof(int) байтов

C++ предлагает и std::array, но не обнуляет массив. Элементы vector<int> stat(26) равны нулю, а array<int, 26> stat - нет. array больше похож на массив языка Си, чем vector.

Посчитаем буквы с помощью std::map

bool areAnagrams(const string &lhs, const string &rhs) {
    if (lhs.size() != rhs.size()) {
        return false;
    }

    map<char, int> stat;
    for (char c: lhs) {
        ++stat[c];
    }
    for (char c: rhs) {
        --stat[с];
    }
    for (const auto&[c, num]: stat) {
        if (0 != num) {
            return false;
        }
    }

    return true;
}

• Время: O(n * log(n)), потому что map::operator[] работает за O(log(n))

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

Посчитаем буквы с помощью std::multiset

bool areAnagrams(const string &lhs, const string &rhs) {
    if (lhs.size() != rhs.size()) {
        return false;
    }

    multiset<char> stat;
    for (char c: lhs) {
        ++stat.insert(c);
    }
    for (char c: rhs) {
        auto iter = stat.find(c);
        if (stat.end() == iter) {
            return false;
        }
        stat.erase(iter);
    }
    
    return stat.empty();
}

• Время: O(n * log(n)), потому что multiset::insert и multiset::find работают за log(n)

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

Упорядочим буквы слов по возрастанию и сравним

bool areAnagrams(string lhs, string rhs) {
    if (lhs.size() == rhs.size()) {
        // O(log(n))
        sort(lhs.begin(), lhs.end());
        // O(log(n))
        sort(rhs.begin(), rhs.end());

        // O(n)
        return lhs == rhs;
    }

    return false;
}

• Время: O(log(n) + log(n) + n) - оставляем большее слагаемое, получим O(n)

• Память: O(n), потому что копирует строки

Ищем границы групп - пары "не анаграмм"

vector<string> removeAnagrams(vector<string>& words) {
    int write = 1;
    for (int prev = 0, next = 1; next < words.size(); ++prev, ++next) {
        if (!areAnagrams(words[prev], words[next])) {
            words[write++] = words[next];
        }
    }
    words.resize(write);
    return words;
}

Теперь не могу вызвать std::swap, потому что prev укажет на слово next на следующем шаге цикла.

Выбираем лучший алгоритм

Говорят "Алгоритм работает за время ". Звучит, словно мы знаем время работы алгоритма, но это не так.

означает размер входных данных алгоритма, например, размер массива words в задаче. Время работы алгоритма растет не быстрее, чем функция , когда мы увеличиваем . Алгоритм справится с ростом лучше, чем алгоритм .

Leetcode сообщает "твое решение работает за 1 мс - это быстрее 90% других". Это разовое измерение. Это значит, что твой алгоритм - лучший по сложности , но в этот раз не повезло. Запусти еще раз, и тот же код способен отработать за 0 мс.

Выбирайте лучший по сложности алгоритм и заставьте работать. Не думайте о времени работы программы, пока не написали программу верно.

Говорим "Нет!" преждевременной оптимизации

Я оптимизировал вызов areAnagrams. Цикл снова и снова сравнивает words[begin] с другим словом, поэтому я сортировал words[begin] однажды, а в areAnagrams сортировал только второе слово:

    while (begin < words.size()) {
        string sample = words[begin];
        sort(sample.begin(), sample.end());
        while (end < words.size() && isAnagram(sample, words[end])) {
            ++end;
        }
        //...
    }

//...

bool isAnagram(const string &sample, string test) {
    if (sample.size() == test.size()) {
        sort(test.begin(), test.end());
        return sample == test;
    }

    return false;
}

Оказалось, что решение без оптимизации

bool areAnagrams(string lhs, string rhs) {
    if (lhs.size() == rhs.size()) {
        sort(lhs.begin(), lhs.end());
        sort(rhs.begin(), rhs.end());

        return lhs == rhs;
    }

    return false;
}

все равно работает за 0 мс и бьет других решений.