Есть ли эффективное решение этого вопроса интервью кодирования?

Question

Нам даны две строки, которые действуют как поисковые запросы. Нам нужно определить, одинаковы ли они. Например:

Запрос 1: курс акций

Запрос 2: курс акций

Нам также предоставляется список, в котором каждая запись содержит два слова, которые являются синонимами. , слова могут повторяться, означая, что существует транзитивное отношение. Примерно так:

[

[стоимость, цена]

[курс, цена]

[доля, капитал]

]

Цель состоит в том, чтобы определить, означают ли запросы одно и то же.

Я предложил решение, в котором я группирую похожие по значению слова в списки и выполняю исчерпывающий поиск, пока не найдем слово из query1. и затем поиск в его группе слова из запроса 2. Но интервьюер хотел более эффективный подход, который я не мог понять. Есть ли более эффективный способ решить эту проблему?

Answer 1

Вот решение, которое позволило бы определить, похожи ли 2 запроса в почти постоянное время (O(size of queries)), с предварительным вычислением в O(number of words in database).

Предварительным вычислением: мы предполагаем, что у вас есть список списки синонимов L

function build_hashmap(L):
    H <- new Hashmap()
    i <- 0
    for each  synonyms_list in L do:
        for each word in synonyms_list do:
            H[word] <- i
        i <- i+1
    return H

Теперь мы можем проверить, являются ли два слова синонимами, используя H

function is_synonym(w1, w2, H):
    if H[w1] == H[w2]:
        return true
    else:
        return False

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

Редактировать:
Быстрое решение может заключаться в реализации алгоритма union-find ' для построения хэш-карты.

Другим способом было бы сначала смоделировать слова как вершины графа и добавить ребра для отношений синонимичности. Затем вы можете построить свою хэш-карту, найдя связанные компоненты графика . Найти связанные компоненты в графе можно, пройдя его.