word-ladder.md

Word Ladder

Jan 11, 2021 · 3 min read

Даны два слова: начальное и конечное, а также словарь различных слов. Вернуть длину кратчайшего пути между начальным и конечным словом, если разрешен следующий переход:

• можно изменить любой ровно один символ
• слово должно быть из словаря

Если такая трансформация невозможна — вернуть ноль.

Задача на LeetCode.

Решение #

Эта задача, по-моему, классический пример на графы. Слова из словаря + начальное слово — вершины, а описанный переход — рёбра.

Рассмотрим пример.

Начальное слово: "hit"
Конечное слово: "cog"
Словарь: ["hot","dot","dog","lot","log","cog"]

Кратчайший путь (один из) “hit” -> “hot” -> “dot” -> “dog” -> “cog”, состоит из 5 слов.

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

Нахождения кратчайшего пути между двумя вершинами — это поиск в ширину (BFS). По аналогии с задачей про апельсины, которую я разбирал раннее.

Почему поиск в ширину всегда находит кратчайший путь?

Мы смотрим на деток каждой вершины прежде чем идти дальше, используя очередь. Если мы нашли нужный нам узел — быстрее до него никак не добраться, разве что перепрыгивая через какие-то вершины, но так нельзя.

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

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
  const words = wordList.concat(beginWord);
  const graph = buildGraph(words);

  // в очереди изначально лежит вершина с которой начинаем поиск,
  // т.е. начальное слово, а также количество пройдённых вершин
  const q = [[beginWord, 1]];

  while (q.length > 0) {
    // снимаем следующий узел с начала очереди,
    // важно соблюдать правильный порядок (т.е. класть в конец, снимать с начала),
    // только тогда мы гарантируем нахождения кратчайшего пути — так работает BFS
    const [node, path] = q.shift();

    // как только нашли конечное слово,
    // можно сразу останавливать поиск
    if (node === endWord) {
      return path;
    }
    // закидываем всех деток в конец очереди
    for (const child of graph[node]) {
      q.push([child, path + 1]);
    }
    // затираем только что посещённую вершину,
    // чтобы избежать зацикливания
    graph[node] = [];
  }
  // если обошли все вершины,
  // но так и не нашли конечного слова,
  // то его там просто не было
  return 0;
};

function buildGraph(words) {
  const result = {};

  // чтобы построить граф нужно пробежать по всем словам,
  // и найти переходы между ними — разница в один символ
  for (let i = 0; i < words.length; i++) {
    result[words[i]] = [];
    for (let j = 0; j < words.length; j++) {
      if (isOneCharDiff(words[i], words[j])) {
        result[words[i]].push(words[j]);
      }
    }
  }
  return result;
}

function isOneCharDiff(s1, s2) {
  let changes = 0;
  for (let i = 0; i < s1.length; i++) {
    if (s1[i] !== s2[i]) {
      changes++;
    }
  }
  return changes === 1;
}

Слегка можно ускориться, если в isOneCharDiff сделать ранний выход из функции — как только количество различных символов больше 1 можно дальше не считать.

function isOneCharDiff(s1, s2) {
- let changes = 0;
+ let result = false;
  for (let i = 0; i < s1.length; i++) {
    if (s1[i] !== s2[i]) {
-     changes++;
+     if (result) {
+       return false;
+     }
+     result = true;
    }
  }
- return changes === 1;
+ return result;
}

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

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