Union-Find Leetcode вопрос превышает лимит времени

Question

Я решаю эту проблему с помощью leetcode https://leetcode.com/problems/sentence-similarity-ii/description/, который включает в себя реализацию алгоритма объединения-поиска, чтобы выяснить, схожи ли два предложения, или нет списка пар, представляющих похожие слова. Я реализовал ранжированное объединение-поиск, где я отслеживаю размер каждого подмножества и присоединяю меньшее поддерево к большему, но по какой-то причине код все еще превышает ограничение по времени. Может кто-то указать мне, что я делаю неправильно Как это можно оптимизировать дальше. Я видел, что другие принятые решения использовали такой же ранжированный алгоритм поиска объединения.

Вот код:

    string root(map<string, string> dict, string element) {
    if(dict[element] == element)
        return element;
    return root(dict, dict[element]);
}
bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>> pairs) {
    if(words1.size() != words2.size()) return false;
    std::map<string, string> dict;
    std::map<string, int> sizes;
    for(auto pair: pairs) {
        if(dict.find(pair.first) == dict.end()) {
            dict[pair.first] = pair.first;
            sizes[pair.first] = 1;
        }
        if(dict.find(pair.second) == dict.end()) {
            dict[pair.second] = pair.second;
            sizes[pair.second] = 1;
        }

        auto firstRoot = root(dict, pair.first);
        auto secondRoot = root(dict, pair.second);
        if(sizes[firstRoot] < sizes[secondRoot]) {
            dict[firstRoot] = secondRoot;
            sizes[firstRoot] += sizes[secondRoot];
        }
        else {
            dict[secondRoot] = firstRoot;
            sizes[secondRoot] += sizes[firstRoot];
        }
    }


    for(int i = 0; i < words1.size(); i++) {
        if(words1[i] == words2[i]) {
            continue;  
        }
        else if(root(dict, words1[i]) != root(dict, words2[i])) {
            return false;
        }
    }
    return true;
}

Спасибо!

Answer 1

Ваша находка в союзе разбита по сложности. Пожалуйста, прочитайте Википедия: Структура данных с несвязным набором .

Чтобы union-find имел сложность, близкую к O (1), он должен использовать сжатие путей. Для этого ваш root метод должен:

1. Получите dict по ссылке, чтобы он мог его изменить.
2. Сделать сжатие пути для всех элементов на пути, чтобы они указывали на корень.

Без сжатия у вас будет сложность O (log N) для root(), что может быть в порядке. Но для этого вам нужно исправить это так, чтобы root() получал dict по ссылке, а не по значению. Передача dict по стоимости стоит O (N).

Тот факт, что dict является std::map, делает любой запрос стоимостью O (log N) вместо O (1). std::unordered_map стоит O (1), но на практике для N <1000 <code>std::map быстрее. Также, даже если используется std::unordered_map, хеширование строки стоит O (len (str)).

Если данные большие, а производительность все еще низкая, вы можете выиграть от работы с индексами в pairs вместо строк и запустить union-find с индексами в vector<int>. Это подвержено ошибкам, так как вы должны правильно обрабатывать дубликаты строк.