{"challenge":{"difficulty":7,"created_at":"2020-12-17T20:54:55.744Z","updated_at":"2022-07-24T21:47:24.837Z","slug":"climbing-the-word-ladder","title":"Climbing the Word Ladder","question":"Imagine two words placed at the two ends of a ladder. Can you reach one word from another using intermediate words as rings of the ladder? Each successive or transition word has a difference of only one letter from its predecessor, and must belong to a provided dictionary. Can we achieve this using the shortest possible number of rings, and return that number?\n\n\u003cimg src=\"https://i.ibb.co/VShnjpd/ladder1.png\"\u003e\n\n## The Problem \n\nSuppose we are given:\n\n- a dictionary of words\n- a **start word**\n- an **end word**\n\nWe have to find a minimum length sequence of words so that the start word is *transformed* into the end word. A word is only transformable to the other if they have a difference of one letter. Consider a dictionary, start word `startW`, and end word `endW` below:\n\n```\nDictionary: {hope, hole, bold, hold, cold, sold, dold}\nstartW: bold\nendW: hope\n```\n\nTwo possible sequences of transformations are given below:\n\n```\nSequence 1: bold-\u003ecold-\u003esold-\u003ehold-\u003ehole-\u003ehope\nSequence 2: bold-\u003ehold-\u003ehole-\u003ehope\n```\n\nThe length of the second sequence is `4`, which is shorter than sequence 1 with a length of `6`. Hence the acceptable answer is 4. We make the following assumptions for this problem:\n\n1. All words in the dictionary are of the same length.\n2. The end word is present in the dictionary. If it is not present, 0 is returned.\n3. The comparison with words in the dictionary is case sensitive. So `abc` is not the same as `ABC`.\n\n### Constraints\n\n- The number of words in the dictionary \u003c= `50`\n- The length of each word in the dictionary and start word \u003c= `50`\n- The strings will only consist of lowercase and uppercase letters\n- Let `n` be the length of each word and `m` be the number of words\n- Expected time complexity :` O((m^2)*n)`\n- Expected space complexity : `O(m*n)`","id":"7496301d-1a0a-4370-a6b7-6ae0915413b5","sequence":105,"has_trace":false,"kind":"algorithms","video":null,"locked":false,"environment":null,"body":"","image_url":"https://storage.googleapis.com/algodailyrandomassets/tutorials-optimized/ladder1.png","published":true,"newsletter_sequence":105,"section_id":25,"video_thumbnail":null,"video_duration":null,"excerpt":"Imagine two words placed at the two ends of a ladder. Can you reach one word from another using intermediate words as rings of the ladder? Each successive or transition word has a difference of only one letter from its predecessor, and must belong to a provided dictionary. Can we achieve this using the shortest possible number of r","initialCode":"```js\nvar assert = require('assert');\n\nfunction wordLadder(begin, end, wordList) {\n  // fill this in\n}\n\ntry {\n  assert.equal(\n    wordLadder('bold', 'hope', [\n      'hope',\n      'hole',\n      'bold',\n      'hold',\n      'cold',\n      'sold',\n      'dold',\n    ]),\n    4\n  );\n\n  console.log(\n    'PASSED: ' +\n      \"`wordLadder('bold', 'hope', ['hope', 'hole', 'bold', 'hold', 'cold', 'sold', 'dold'])` should return `4`\"\n  );\n} catch (err) {\n  console.log(err);\n}\n\n```","language_content_id":513,"languages_supported":[34,29,26,10,16,22,68],"solutionCode":"```js\nvar assert = require('assert');\n\nfunction wordLadder(begin, end, wordList) {\n  let len = 1;\n  let queue = [begin];\n  const dict = new Set(wordList);\n  const seen = new Set(queue);\n\n  while (queue.length) {\n    const next = [];\n    for (let node of queue) {\n      if (node === end) {\n        return len;\n      }\n\n      const splitNode = node.split('');\n      for (let i = 0; i \u003c splitNode.length; i++) {\n        for (let d = 0; d \u003c 26; d++) {\n          splitNode[i] = String.fromCharCode(97 + d);\n          const nv = splitNode.join('');\n          if (!seen.has(nv) \u0026\u0026 dict.has(nv)) {\n            next.push(nv);\n            seen.add(nv);\n          }\n          splitNode[i] = node[i];\n        }\n      }\n    }\n    queue = next;\n    len++;\n  }\n\n  return 0;\n}\n\ntry {\n  assert.equal(\n    wordLadder('bold', 'hope', [\n      'hope',\n      'hole',\n      'bold',\n      'hold',\n      'cold',\n      'sold',\n      'dold',\n    ]),\n    4\n  );\n\n  console.log(\n    'PASSED: ' +\n      \"`wordLadder('bold', 'hope', ['hope', 'hole', 'bold', 'hold', 'cold', 'sold', 'dold'])` should return `4`\"\n  );\n} catch (err) {\n  console.log(err);\n}\n\n```","tests":[{"id":1781,"text":"`wordLadder('bold', 'hope', ['hope', 'hole', 'bold', 'hold', 'cold', 'sold', 'dold'])` should return `4`","test_string":"assert.equal(\r\n  wordLadder('bold', 'hope', [\r\n    'hope',\r\n    'hole',\r\n    'bold',\r\n    'hold',\r\n    'cold',\r\n    'sold',\r\n    'dold',\r\n  ]),\r\n  4\r\n);","language_content_id":513,"screen_id":null,"created_at":"2020-12-17T22:26:53.033Z","updated_at":"2020-12-17T22:39:10.006Z"}]},"completed":null,"screens":[{"id":1801,"kind":"question","options":[],"content":"Imagine two words placed at the two ends of a ladder. Can you reach one word from another using intermediate words as rings of the ladder? Each successive or transition word has a difference of only one letter from its predecessor, and must belong to a provided dictionary. Can we achieve this using the shortest possible number of rings, and return that number?\n\n\u003cimg src=\"https://i.ibb.co/VShnjpd/ladder1.png\"\u003e\n\n## The Problem \n\nSuppose we are given:\n\n- a dictionary of words\n- a **start word**\n- an **end word**\n\nWe have to find a minimum length sequence of words so that the start word is *transformed* into the end word. A word is only transformable to the other if they have a difference of one letter. Consider a dictionary, start word `startW`, and end word `endW` below:\n\n```\nDictionary: {hope, hole, bold, hold, cold, sold, dold}\nstartW: bold\nendW: hope\n```\n\nTwo possible sequences of transformations are given below:\n\n```\nSequence 1: bold-\u003ecold-\u003esold-\u003ehold-\u003ehole-\u003ehope\nSequence 2: bold-\u003ehold-\u003ehole-\u003ehope\n```\n\nThe length of the second sequence is `4`, which is shorter than sequence 1 with a length of `6`. Hence the acceptable answer is 4. We make the following assumptions for this problem:\n\n1. All words in the dictionary are of the same length.\n2. The end word is present in the dictionary. If it is not present, 0 is returned.\n3. The comparison with words in the dictionary is case sensitive. So `abc` is not the same as `ABC`.\n\n### Constraints\n\n- The number of words in the dictionary \u003c= `50`\n- The length of each word in the dictionary and start word \u003c= `50`\n- The strings will only consist of lowercase and uppercase letters\n- Let `n` be the length of each word and `m` be the number of words\n- Expected time complexity :` O((m^2)*n)`\n- Expected space complexity : `O(m*n)`","code":null,"full_screen":false,"solution":null,"lesson_id":null,"challenge_id":"7496301d-1a0a-4370-a6b7-6ae0915413b5","sequence":1,"title":"Description","slug":"description","created_at":"2020-12-17T20:54:43.130Z","updated_at":"2023-01-07T17:39:07.921Z","explanation":null,"summary":" The problem is to find the shortest sequence of words with a one letter difference between successive words, which transforms a given `startW` to a given `endW` using words from a provided dictionary, with `time complexity` of `O((m^2)*n)` and `space complexity` of `O(m*n)`."},{"id":1802,"kind":"info screen","options":[],"content":"We can look at this problem as a `search` problem of an undirected graph, where each node represents a word. We'll denote the start state by `startW` and goal state by `endW`. Two adjacent nodes are those that can be transformed into one another and have a difference of only one character.\r\n\r\nTo find the shortest sequence of words from the start to the goal state, we'll do a breadth first search. To implement breadth first search, a queue data structure is required. The figure below shows how search proceeds. The start state is `four` and goal state is `hoop`. The search is initialized by pushing the word `four` into the queue. \r\n\r\nThe search algorithm pops each word from the queue in a first in first out manner. In our example, the `four` is popped and its adjacent words are searched in the dictionary.  Three such words are found, i.e., `foum`, `hour` and `cour`, which are again pushed into the queue one by one. This process is repeated till either the goal state is found or the entire dictionary has been searched.\r\n\r\nNote that a search tree is implicitly being built, i.e., it is not physically present in memory, but its implicit representation is there. The queue is the data structure that keeps track of all nodes that need to be explored in a breadth first manner. This queue is also shown in the figure as `Q`.\r\n\r\n\u003cimg src=\"https://i.ibb.co/M1tWS7z/ladder2.png\" /\u003e","code":null,"full_screen":true,"solution":null,"lesson_id":null,"challenge_id":"7496301d-1a0a-4370-a6b7-6ae0915413b5","sequence":2,"title":"Our Explanation","slug":"our-explanation","created_at":"2020-12-17T22:20:37.520Z","updated_at":"2023-01-07T17:39:10.844Z","explanation":null,"summary":" We can solve the problem of finding the shortest sequence of words between a start state `startW` and a goal state `endW` by using a `queue` data structure to do a **breadth first search** on an undirected graph."},{"id":1804,"kind":"info screen","options":[],"content":"## The Pseudo-Code\r\n\r\nThe pseudo-code here is a representation of the search procedure.\r\n\r\n## Time Complexity\r\n\r\nTo find whether or not two words are adjacent, `n` comparisons are required, where `n` is the length of each word. In the worst-case scenario, all pairs of words would be compared by making \\(O(m^2)\\) comparisons. If there are `m` words, the time complexity is \\(O(m^2n)\\). We are using the queue data structure, which in the worst-case scenario would have `m` entries, making the space complexity `O(mn)`. \r\n\r\n## Concluding Remarks\r\n\r\nWe have described a simple algorithm based on breadth first search to solve the `word ladder`. The algorithm can be made more efficient by pre-processing and using a more complex data structure to store an intermediate representation of words that would make searching through the dictionary more efficient and faster. However, this would be at the cost of increasing the space complexity.","code":"```\nMethod: solve\nInput: startW, endW, dictionary\n\nData structure: Queue Q of nodes.\n               Node data is called strNode that keeps track of the word and level\n\n1. level = 1\n2. Add to the end of queue (startW,level). \n3. Remove from dictionary (startW)\n4. Repeat till endW found or dictionary is empty\n    i.   Remove word w and level from front of queue\n    ii.  Search dictionary for all words adjacent to w \n    iii. If an adjacent word is endW then stop\n    iv.  level = level+1\n    iv.  Add to the end of queue all adjancent (word,level) pairs\n    v.   Remove all adjacent words from dictionary\n5. Return level\n```","full_screen":false,"solution":null,"lesson_id":null,"challenge_id":"7496301d-1a0a-4370-a6b7-6ae0915413b5","sequence":3,"title":"Pseudocode","slug":"pseudocode","created_at":"2020-12-17T22:22:27.638Z","updated_at":"2023-01-07T17:39:13.118Z","explanation":null,"summary":" The **word ladder** can be solved with a simple **breadth-first search** algorithm with a time complexity of \\(O(m^2n)\\) and space complexity of `O(mn)`."},{"id":5727,"kind":"info screen","options":[],"content":"## One Pager Cheat Sheet\n\n- The problem is to find the shortest sequence of words with a one letter difference between successive words, which transforms a given `startW` to a given `endW` using words from a provided dictionary, with `time complexity` of `O((m^2)*n)` and `space complexity` of `O(m*n)`.\n- We can solve the problem of finding the shortest sequence of words between a start state `startW` and a goal state `endW` by using a `queue` data structure to do a **breadth first search** on an undirected graph.\n- The **word ladder** can be solved with a simple **breadth-first search** algorithm with a time complexity of \\(O(m^2n)\\) and space complexity of `O(mn)`.","code":null,"full_screen":true,"solution":null,"lesson_id":null,"challenge_id":"7496301d-1a0a-4370-a6b7-6ae0915413b5","sequence":4,"title":"One Pager Cheat Sheet","slug":"algodaily-cheatsheet","created_at":"2023-01-07T17:39:08.091Z","updated_at":"2023-01-07T17:39:08.091Z","explanation":null,"summary":null}],"beforeArr":["Challenge","two-stack-queue"],"nextArr":["Lesson","what-is-the-linked-list-data-structure"],"companies":["databricks","twilio","gitlab","thoughtspot","sumo-logic","pipedrive","zoom","sonos"],"section":{"id":25,"title":"Queues Interview Questions","slug":"queues-interview-questions","sequence":12,"description":"In this section, we'll look at how `queue`s work and how to use them in your interviews and in writing programs.\n\nQueues work by storing data items in the order they arrive, and removing or processing them in the same order. This is known as first-in, first-out (**FIFO**) processing. They have many different uses, but developers often find them especially useful when it comes to doing some work in order, or in the background while keeping the main program/thread unblocked. They're very similar to stacks, which are LIFO (last-in, first-out) structures.","created_at":"2021-04-29T02:39:53.853Z","updated_at":"2022-08-15T17:43:05.969Z","image_url":"https://storage.googleapis.com/algodailyrandomassets/curriculum/cheatsheet/queue.png","course_id":3,"published":true,"locked":true,"time":"1.3 hours","code_snippets_count":41,"visuals_count":24,"free_tutorials":2,"videos_count":3},"sections":[{"id":25,"title":"Queues Interview Questions","slug":"queues-interview-questions","sequence":12,"description":"In this section, we'll look at how `queue`s work and how to use them in your interviews and in writing programs.\n\nQueues work by storing data items in the order they arrive, and removing or processing them in the same order. This is known as first-in, first-out (**FIFO**) processing. They have many different uses, but developers often find them especially useful when it comes to doing some work in order, or in the background while keeping the main program/thread unblocked. They're very similar to stacks, which are LIFO (last-in, first-out) structures.","created_at":"2021-04-29T02:39:53.853Z","updated_at":"2022-08-15T17:43:05.969Z","image_url":"https://storage.googleapis.com/algodailyrandomassets/curriculum/cheatsheet/queue.png","course_id":3,"published":true,"locked":true,"time":"1.3 hours","code_snippets_count":41,"visuals_count":24,"free_tutorials":2,"videos_count":3}],"screen_completions":[]}