Concatenated Words

Дан массив слов без дубликатов. Нужно найти среди них такие, которые могут быть составлены конкатенацией других слов (как минимум, двух).

Решение #

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

function canSplit(word, concatsCount = 0) {
  // базовый случай для рекурсии:
  // нет строки, то есть проверили все префиксы
  if (word.length === 0) {
    // считаем, что можно разбить,
    // если для этого сделали больше
    // чем одну конкатенацию,
    // (то есть конкатенацию самого
    // этого слова с пустой строкой)
    // а иначе это будет просто
    // исходное слово
    return concatsCount > 1;
  }
  for (let i = 0; i < words.length; i++) {
    if (
      // если нашли слово, которое является префиксом
      word.indexOf(words[i]) === 0 &&
      // рекурсивно поищем как разбить оставшуюся строку
      canSplit(word.substring(words[i].length), concatsCount + 1)
    ) {
      // если удалось найти — отлично, сразу вернём true,
      // если не удалось, то поиск должен продолжиться
      // в цикле выше
      return true;
    }
  }
  return false;
}

В чем проблема данного решения? В скорости.

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

for (let i = 0; i < words.length; i++) {
+ if (words[i].length > word.length) {
+   break;
+ }
}

Попробуем сдать — получаем stackoverflow 🤔

В условии сказано, что длина слов может быть 0 <= words[i].length <= 1000, а значит пустая строка разрешена. В случае с пустой строкой canSplit зацикливается.

if (
    // пустая строка всегда заматчится на начало,
    word.indexOf(words[i]) === 0 &&
    // а substring от нуля даёт ту же строку,
    // как следствие — бесконечный цикл
    canSplit(word.substring(words[i].length), concatsCount + 1)
)

⚠️ Нужно проверять код на краевые случаи, то есть что будет при пустой строке, и длины 1000.

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

Правим баг:

if (
+   words[i].length > 0 &&
    word.indexOf(words[i]) === 0 &&
    canSplit(word.substring(words[i].length), concatsCount + 1)
)

Сдаём и получаем TLE — то есть программа работает слишком долго.

Где «бутылочное горлышко»? Копирование строк? Да, но на самом деле, это не самый большой слон в этой комнате.

function canSplit(curr, suffixStart = 0, slicesCount = 0) {
  if (words[curr].length === suffixStart) {
    return slicesCount > 1;
  }
  for (let i = 0; i < words.length; i++) {
    if (words[i].length > words[curr].length) {
      break;
    }
    if (
      words[i].length > 0 &&
      words[curr].indexOf(words[i], suffixStart) === suffixStart &&
      canSplit(curr, suffixStart + words[i].length, slicesCount + 1)
    ) {
      return true;
    }
  }
  return false;
}

Переписать без копирования строк — само по себе неплохое упражнение. Однако, при попытке сдать получаем всё тот же TLE.

На самом деле, основная проблема — поиск подстроки, а именно:

words[curr].indexOf(words[i], suffixStart) === suffixStart;

То есть мы пробегаемся по всем словам, и для каждого из них пытаемся заматчить префикс, что даёт O(N * M) сложность по времени, где N количество слов, а M длина слова. И это на каждый canSplit!

Здесь на помощь приходят префиксные деревья (trie).

Суть в том, что можно построить дерево из указанных слов таким образом, что префиксы сложатся в определённые пути в этом дереве.

Нам не придётся каждый раз бегать по всем словам в поиске префиксов — достаточно найти путь в этом дереве до узла isLeaf (то есть конца слова)!

Мне это представляется как есть огромный массив слов, и мы их сложили одно на другое, так что общие префиксы разных слов «растворились» в этом дереве.

На указанном пример: dog, cat, dogcatdog

Мы сперва найдем путь от корня до g, то есть слово dog. Далее продолжим поиск для суффикса catdog, снова от корня дерева. И так далее.

Найдется префикс или нет — зависит от того дойдём ли мы до узла isLeaf или придём в тупик, что означает в словаре не было слов с таким префиксом.

/**
 * Класс для работы с префиксным деревом.
 * Содержим один публичный метод — добавить слово.
 */
class Trie {
  root = new Node("");
  // добавляем указанное слово в дерево
  add(word) {
    let curr = this.root;

    for (let i = 0; i < word.length; i++) {
      curr = curr.addNext(word[i]);
    }
    curr.isLeaf = true;
  }
}

/**
 * Класс для работы с узлом.
 * Позволяет добавлять и искать по деткам.
 */
class Node {
  isLeaf = false;
  children = new Array(26);
  constructor(val) {
    this.val = val;
  }
  // добавляем следующий узел
  addNext(val) {
    const idx = this._idx(val);
    if (!this.children[idx]) {
      this.children[idx] = new Node(val);
    }
    return this.children[idx];
  }
  // ищем указанный символ
  getNext(val) {
    return this.children[this._idx(val)];
  }
  _idx(val) {
    return val.charCodeAt(0) - "a".charCodeAt(0);
  }
}

Тогда canSplit можно переписать следующим образом.

function canSplit(curr, suffixStart = 0, slicesCount = 0) {
  if (words[curr].length == suffixStart) {
    return slicesCount > 1;
  }
  // начинаем поиск от корня дерева,
  // обратите внимание, что кейс с пустой
  // строкой автоматически покрывается:
  // корень дерева и есть пустая строка,
  // и мы начинаем поиск со следующих за ней
  // символах
  let node = trie.root;

  // ищем, начиная с указанного индекса
  for (let i = suffixStart; i < words[curr].length; i++) {
    // берем очередного кандидата
    node = node.getNext(words[curr][i]);
    // есть ли следующая буква среди префиксов?
    // если зашли в тупик — дальше искать смысла нет
    if (!node) {
      return false;
    }
    // isLeaf означает, что указанный
    // префикс был среди слов в словаре,
    // значит начиная отсюда надо поискать
    // разбиение для суффикса
    if (node.isLeaf && canSplit(curr, i + 1, slicesCount + 1)) {
      return true;
    }
  }
  return false;
}

Теперь сложность данного решения ограничена только глубиной дерева, то есть самым длиным словом! Это намного быстрее чем дёргать indexOf для каждого слова из списка.

Всё вместе.

/**
 * @param {string[]} words
 * @return {string[]}
 */
var findAllConcatenatedWordsInADict = function(words) {
  const trie = new Trie();

  function canSplit(curr, suffixStart = 0, slicesCount = 0) {
    if (words[curr].length == suffixStart) {
      return slicesCount > 1;
    }
    let node = trie.root;

    for (let i = suffixStart; i < words[curr].length; i++) {
      node = node.getNext(words[curr][i]);
      if (!node) {
        return false;
      }
      if (
          node.isLeaf &&
          canSplit(curr, i + 1, slicesCount + 1)
        ) {
        return true;
      }
    }
    return false;
  }
  const result = [];

  words.sort((a, b) => a.length - b.length);

  for (let i = 0; i < words.length; i++) {
    // трюк с отсечением поиска
    // по заведомо невозможным префиксам
    // имеет смысл добавлять в дерево только слова,
    // которые короче проверяемого
    if (canSplit(i)) {
      result.push(words[i]);
    } else {
      trie.add(words[i]);
    }
  }
  return result;
};

class Trie {
  // ...
}

class Node {
  // ...
}

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

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