Сортировать массив строк на основе совпадения слов с входной строкой

Question

Мне не удалось найти решение нижеприведенной проблемы в конкурсе кодов.

Проблема: у нас есть строка ввода "хороших слов", разделенных подчеркиванием и списком отзывов пользователей (в основном массив строк, гдекаждый элемент массива имеет несколько слов, разделенных подчеркиванием).Мы должны отсортировать список отзывов пользователей так, чтобы элементы с большим количеством хороших слов были на первом месте.

Example:

input:

good words: "pool_clean_food".

user review array:["food_bedroom_environment","view_sea_desert","clean_pool_table"].

output: [2,0,1]

Explanation:

Array[2]="clean_pool_table" having 2 good words i.e. pool and clean
Array[0]="food_bedroom_environment" having 1 good word i.e. food
Array[1]="view_sea_desert" having 0 good word i.e. nil

How can I approach the problem, which data structure shall I use so that my code can handle large inputs?

Answer 1

• Разделить слова ввода хорошие слова на подчеркивание и сохранить их в хэш-наборе.

• Теперь для каждого отзыва присвойте оценку0 изначально.также разделите слова по подчеркиванию и проверьте, присутствуют ли слова в хэш-наборе одно за другим.Если слово присутствует, добавьте 1 к оценке этого слова.

• Теперь рассмотрите все отзывы как пару <review, score> и отсортируйте их по значению их оценки в порядке возрастания.Для этого вы можете использовать любой стандартный алгоритм сортировки O(nlogn).

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