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();
};

Без копирования строк намного лучше!

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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