Разбираем задачу № 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):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function numWays(words: string[], target: string):number { const WL = words[0].length; // всего 26 разных букв латинского алфавита // и каждая может встречаться на определенной "глубине" слов словаря const char: number[][] = new Array(26) for (let i = 0; i < 26; i ++) char[i] = new Array(WL).fill(0) for (let word of words) { for (let i = 0; i < WL; i ++) { const ind = word.charCodeAt(i) - 97 char[ind][i] ++; } } ... } |
Пример 4
Рассмотрим входные данные words = [‘acca’,’bbbb’,’caca’], target = ‘aba’.
Массив char будет выглядеть вот так:
|
1 2 3 4 5 |
[ [1,1,0,2], // a [1,1,1,1], // b ... // другие буквы, которые нам не нужны ] |
Что если мы будем искать решение задачи, начиная с простой задачи и, используя решение предыдущего случая, усложнять задачу, пока не придем к полному решению?
Вместо 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.
|
1 2 3 |
[1, 2, 2, 4] [0, 1, 3, 5] [0, 0, 0, 6] |
Решением задачи является нижний правый коэффициент, соответствующий полной глубине словаря и всему слову target. Обозначим массив как DP.
Формула для следующего шага получится следующая:
DP[i][j] = DP[i][j-1] + DP[i-1][j-1] * char[j]
Фактически, мы использовали здесь динамическое программирование, форму рекурсивного алгоритма с памятью.
Задачу можно решать и с помощью обычной рекурсии, но основная сложность в том, чтобы выбрать оптимальным образом перекрывающиеся задачи, так чтобы запоминать лишь необходимый минимум под-решенией для решения всей задачи.
Посмотрим как это выглядит в коде:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
function numWays(words: string[], target: string): number { // подготовительный этап мы уже рассмотрели // нужно подсчитать число букв в словаре const WL = words[0].length; const char: number[][] = new Array(26) for (let i = 0; i < 26; i ++) char[i] = new Array(WL).fill(0) for (let word of words) { for (let i = 0; i < WL; i ++) { const ind = word.charCodeAt(i) - 97 char[ind][i] ++; } } // вообще нам не нужен массив длиной во всё слово target, // т.к. при вычислениях мы используем только два смежных // индекса, но для простоты не будем заниматься // этой оптимизацией памяти const dp: number[][] = new Array(target.length); for (let i = 0; i < target.length; i ++) dp[i] = new Array(WL).fill(0) // внешний цикл по target for (let i = 0; i < target.length; i ++) { // внутренний по глубине словаря const ind = target.charCodeAt(i) - 97 for (let j = i; j < WL; j ++) { // есть еще некоторые граничные условия когда i = 0, // которые мы не обсудили явно, но они очевидны из // тех примеров, которые мы рассмотрели dp[i][j] = (j > 0 ? dp[i][j - 1] : 0) + + (i == 0 ? char[ind][j] : char[ind][j] * dp[i - 1][j - 1]) } } // результат return dp[target.length - 1][WL - 1]; }; |
На литкоде, в условиях задачи есть еще ограничение по величине результата. Его я тоже не стал тут реализовывать, чтобы не захламлять код. Думаю, разберетесь. :)