Задача о подсчете количества путей в словаре

Разбираем задачу № 1639 Number of Ways to Form a Target String Given a Dictionary c leetcode.com. Дан словарь, где слова имеют одинаковую длину — words. Также дано дополнительно слово — target, которое нужно составить из словарных слов по следующим правилам:

Вы можете брать буквы из любого слова words и составлять target, буква за буквой, но если вы взяли букву с позиции j в некотором слове, то следующую букву можно брать только с позиции не меньше чем j + 1.

Требуется вернуть кол-во путей (вариантов), какими возможно составить target.

Решение

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

Пример 1

Пусть дано words = [‘ab’, ‘bb’] и target = ‘b’.

Очевидно, что мы можем взять любую из трех букв ‘b’ в словарных словах, чтобы составить требуемый target. Т.е. ответ — 3 варианта.

Пример 2

Пусть дано words = [‘ab’, ‘ab’] и target = ‘ab’.

Здесь ответ — 4 и, возможно, это не очевидно. Чтобы получить первую букву target (‘a’), мы можем использовать букву ‘a’ любого из слов — т.е. у нас есть два варианта. И для буквы ‘b’ — также получится два варианта. Общее число комбинаций будет состоять из произведения этих комбинаций: 2 * 2 = 4.

Пример 3

Здесь words = [‘acca’,’bbbb’,’caca’], target = ‘ab’

Здесь должно получится 5 вариантов. А также в словаре есть лишняя буква — ‘c’, которую мы не используем.

Чтобы получить первую букву target нам нужна ‘a’, если мы берем её с первой позиции ‘acca’, то для второй буквы в target подойдут только 3 буквы из ‘bbbb‘. Первую ‘b’ мы не можем использовать, т.к. эта позиция нам не доступна после первого шага. У нас получается 1 * 3 вариантов. Но это еще не всё. Мы можем взять букву ‘a’ из ‘caca’, а для выбора буквы ‘b’ останется два варианта — ‘bbbb‘, т.е. ещё два варианта — итого 5. Буквы ‘a’, стоящие в конце слов ‘acca‘ и ‘caca‘ мы не можем использовать уже, т.к. они не оставят нам вариантов для выбора ‘b’.

Пока, я думаю, это не прояснило алгоритм, но понятно, что нам предварительно нужно узнать где, сколько и каких букв мы встречаем в словаре. Если к примеру на позиции j в словаре встречается требуемая нам буква 5 раз, то кол-во вариантов увеличивает в это же кол-во раз.

Давайте выполним этот подсчет. (Как всегда мой любимый typescript):

Пример 4

Рассмотрим входные данные words = [‘acca’,’bbbb’,’caca’], target = ‘aba’.

Массив char будет выглядеть вот так:

Что если мы будем искать решение задачи, начиная с простой задачи и, используя решение предыдущего случая, усложнять задачу, пока не придем к полному решению?

Вместо target, мы будем решать задачу для ‘a’, затем ‘ab’, а потом ‘aba’.

case ‘A’

Массив char для ‘a’, показывает, что всего у нас есть 4 варианта. При этом, если бы длина словаря варьировалась от 1 до 4, то у нас бы получился массив ответов [1, 2, 2, 4]. Т.е. всего 1 вариант при глубине словаря в один символ, и т.д — 4 варианта для полной глубины словаря.

case ‘AB’

Попробуем использовать полученные результаты предыдущего кейса. Снова варьируем длину слов словаря. Если словарь имеет длину 1 [‘a’, ‘b’, ‘c’], то мы не можем составить ‘ab’, — число вариантов всегда 0. При длине словаря равной 2 [‘ac’, ‘bb’, ‘ca’], у нас получится всего 1 вариант. Вообще, он получается как произведение вариантов для case ‘A’ позиции (1), умноженное на кол-во букв ‘b’ на текущей позиции (2), как это видно из разобранных выше примеров. Итого получили 1.

Для позиции 3 [‘acc’,’bbb’,’cac’] мы имеем число вариантов 3. Как оно получается: case ‘A’ равно 2 на предыдущей позиции (2), умножаем на число букв ‘b’ на текущей позиции (3) т.е. = 2 * 1. Но нужно добавить еще число вариантов с case ‘AB’ предыдущего шага, их там было 1. Итог 2 + 1 = 3.

По той же логике для позиции 4 мы получаем число вариантов 5. Все варианты — [0, 1, 3, 5].

case ‘ABA’

Уже не вдаваясь в детали, покажу результат — [0, 0, 0, 6], последняя цифра получается как case ‘AB’[3] * char для ‘a’ в позиции [4] = 3 * 2 = 6.

Переходим к алгоритму

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

Разбирая пример 4, мы рекурсивно вычисляем коэффициенты двумерной матрицы, где по X у нас идет рост глубины словаря, я по Y — длины слова target.

Решением задачи является нижний правый коэффициент, соответствующий полной глубине словаря и всему слову target. Обозначим массив как DP.

Формула для следующего шага получится следующая:

DP[i][j] = DP[i][j-1] + DP[i-1][j-1] * char[j]

Фактически, мы использовали здесь динамическое программирование, форму рекурсивного алгоритма с памятью.

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

Посмотрим как это выглядит в коде:

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

Написать комментарий

Мало букафф? Читайте есчо !

Задача о поиске лучшей сделки

Февраль 2, 2023 г.

Это еще одна классическая задача программирования о поиске некой лучшей пары чисел в массиве. Задача формулируется следующим образом. Есть массив стоимости ...

Читать

Решение задачи оптимизации в направленном графе

Апрель 9, 2023 г.

Сегодня расскажу о решении задачи №1857 с литкода, которая называется как "Largest Color Value in a Directed Graph". Суть задачи: дан направленный ...

Читать

 

Комментарии к «Задача о подсчете количества путей в словаре»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: