Letter Tile Possibilities
Найти количество различных строк, которые можно составить из указанных символов.
Для строки AAB можно получить 8 таких подпоследовательностей: "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".
Решение #
Решение «в лоб» — построить все такие строки, сложить в сет (чтобы не было повторений) и вернуть размер сета.
Каким образом получить нужные строки? Нужно рекурсивно исследовать всё дерево возможных вариантов (подпоследовательностей) — это и есть бектрекинг. С условием того, что нельзя использовать один и тот же символ дважды.
Условие для выхода из рекурсии: длина строки не может быть больше, чем количество доступных символов.
Ещё задача на бектрекинг — про N королев на шахматной доске.
/**
* @param {string} tiles
* @return {number}
*/
var numTilePossibilities = function(tiles) {
// здесь будем хранить
// индексы использованных символов,
// таким образом можно проверять,
// что не используем индекс дважды
const usedIndexes = new Set();
// здесь будем хранить
// текущую подпоследовательность,
// по сути выступает в роли стека —
// будем класть сюда очередной символ
// при заходе в рекурсию и
// снимать при выходе,
// таким образом стек будет
// в каждый момент времени отражать
// узлы в дереве возможных вариантов
const currSeq = [];
// сюда будет складывать все результаты
const result = new Set();
function dfs() {
// условие выхода из рекурсии —
// использовали все доступные символы
if (currSeq.length === tiles.length) {
return;
}
// бежим по всем символам
for (let i = 0; i < tiles.length; i++) {
// если уже использовали символ,
// то дважды его брать нельзя
if (usedIndexes.has(i)) {
continue;
}
// закидываем текущий символ
// в конец стека
currSeq.push(tiles[i]);
// не забываем добавить
// индекс в «использованные»
usedIndexes.add(i);
// сериализуем стек в строку
// и кидаем в результирующий сет,
// который сам позаботится о том,
// чтобы не было повторений
result.add(currSeq.join(""));
// заходим в рекурсию, которая
// создаст следующий ряд узлов в дереве
dfs();
// когда вышли из рекурсии
// надо не забыть почистить текущий стейт:
// снять символ со стека и
// удалить символ из использованных
currSeq.pop();
usedIndexes.delete(i);
}
}
dfs();
// ответ — размер сета с результатами
return result.size;
};
Полезно в таких задачах нарисовать дерево рекурсивных вызовов ручками, перед тем как писать код — станет понятнее как «не использовать один и тот же символ дважды», и когда выходить из рекурсии.
Итак, это решение рабочее, но есть где ускориться.
Если посмотреть внимательно, то сами строки нам и не нужны, просят найти только их количество. Создание и копирование строк — бутылочное горлышко этого решения.
По сути, в дереве возможных вариантов нужно подсчитать количество узлов (рекурсивных вызовов):
- result.add(currSeq.join(''));
+ resultSize++;
Проблема только в том, что строки должны быть без повторений. На изображении выше хорошо видно, что текущий алгоритм найдёт две строки AAB и AAB, потому что A и A там стоят в разном порядке. Строка же получается одна и та же, и не должна быть посчитана дважды.
Итак, нам нужно следить за двумя вещами:
- один и тот же символ не используется дважды;
- одинаковые символы, но в разном порядке, не должны быть посчитаны дважды.
Сейчас мы используем сет с индексами, который справляется только с первым пунктом. Надо найти структуру данных, которая справится сразу с двумя.
Пусть у нас есть строка AA. Сочетания через индексы показывает 12 и 21 — две разные строки. А что если использовать счётчик? Счетчик как раз стирает разницу между положением одинаковых символов!
Счетчик решает сразу две проблемы, описанные выше:
- один и тот же символ не может быть использован дважды — если счетчик равен нулю, то дальше не пойдём
- одинаковые символы в разном порядке — как только мы построили счетчик, то знания о положении символов исчезает, а это как раз то, что нужно
Полезно нарисовать дерево рекурсивных вызовов и убедиться, что дубликаты действительно исключены
/**
* @param {string} tiles
* @return {number}
*/
var numTilePossibilities = function(tiles) {
// 26 возможных символов в задаче
const counters = new Array(26).fill(0);
// удобно сохранит ASCII-код «начала отсчёта»,
// чтобы потом считать индекс буквы
const A = "A".charCodeAt(0);
// считаем все доступные буквы
for (let i = 0; i < tiles.length; i++) {
const charIndex = tiles.charCodeAt(i) - A;
counters[charIndex]++;
}
function dfs() {
let result = 0;
// каждый раз проходимся
// по всем доступным буквам
for (let i = 0; i < 26; i++) {
// если счётчик равен нулю:
// либо такой буквы не было,
// либо мы уже все использовали
if (counters[i] > 0) {
// берем текущий символ в «строку»,
// и идём дальше
counters[i]--;
result += 1 + dfs();
// не забываем «вернуть символ назад»,
// чтобы он мог быть использован
// в других частях дерева
counters[i]++;
}
}
return result;
}
return dfs();
};
Без копирования строк намного лучше!