Word Ladder

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Pseudocode

- initially tried to solve it as a graph question
- still don't know understand solution

Solution

// No idea how this works lol
var ladderLength = function (begin, end, wordList) {
  let set = new Set();
  for (let val of wordList) {
    if (val !== begin) set.add(val);
  }
  if (!set.has(end)) return 0;
  let depth = 0;
  let queue = [begin];
  let size = queue.length;
  let a = "a".charCodeAt(0);
  while (queue.length > 0) {
    depth++;
    while (size > 0) {
      let str = queue.shift();
      for (let i = 0; i < str.length; i++) {
        for (let j = 0; j < 26; j++) {
          let search =
            str.slice(0, i) + String.fromCharCode(a + j) + str.slice(i + 1);
          if (search === str) continue;
          if (search === end) return depth + 1;
          if (set.has(search)) {
            queue.push(search);
            set.delete(search);
          }
        }
      }
      size--;
    }
    size = queue.length;
  }

  return 0;
};
//hit

Time and Space Complexity

Time

What did the code do
Total -

Space

What did the code do
Total -

PreviousFind Median from Data Stream NextBasic Calculator

Last updated 2 years ago

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

// No idea how this works lol var ladderLength = function (begin, end, wordList) { let set = new Set(); for (let val of wordList) { if (val !== begin) set.add(val); } if (!set.has(end)) return 0; let depth = 0; let queue = [begin]; let size = queue.length; let a = "a".charCodeAt(0); while (queue.length > 0) { depth++; while (size > 0) { let str = queue.shift(); for (let i = 0; i < str.length; i++) { for (let j = 0; j < 26; j++) { let search = str.slice(0, i) + String.fromCharCode(a + j) + str.slice(i + 1); if (search === str) continue; if (search === end) return depth + 1; if (set.has(search)) { queue.push(search); set.delete(search); } } } size--; } size = queue.length; } return 0; }; //hit