Количество строк в массиве A, которые можно сделать равными строкам в массиве B путем добавления символов

Опубликовано: 19 Сентября, 2022

Даны два массива строк SearchWord[] и FindWord[] . Задача состоит в том, чтобы проверить, сколько строк в FindWord[] может быть сформировано после следующих операций над как можно большим количеством строк:

  • Выберите строку из SearchWord[] .
  • Добавьте один английский алфавит (которого нет в этой строке).
  • Переставьте строку, как вам нравится.

Примечание. Каждый алфавит в SearchWord[] и FindWord[] уникален и появляется только один раз.

Примеры:

Input: SearchWord = {“ge”, “fo”, “ek”}, FindWord = {“gek”, “for”}
Output: 2
Explanation: ‘k’ can be appended to the “ge” to make “gek” which matches the FindWord[0] 
‘r’ can be appended to the “fo” to make “for” which matches the FindWord[1] 

Input: SearchWord = {“ohr”, “tm”, “ek”}, FindWord = {“mat”, “hr”}
Output: 1

Подход: простой подход к решению этой проблемы заключается в сортировке и использовании техники хеширования.

  • Отсортируйте SearchWord[] и FindWord[] в алфавитном порядке.
  • Примените обратную логику вместо выбора слова из массива SearchWord[], выберите слово из массива FindWord[].
  • И найдите это слово, удаляя символы один за другим и находя соответствующее слово.

Ниже приведена реализация описанного выше подхода.

Сложность времени: O(N*M), где N и M — размер SearchWord[] и FindWord[]
Вспомогательное пространство: НА)

РЕКОМЕНДУЕМЫЕ СТАТЬИ