126. Word Solitaire II

The title

Complete the transformation from beginWord to endWord according to the dictionary wordList. A sequence of transformations representing this process is formally like beginWord -> S1 -> s2 ->… -> sk such a sequence of words, and satisfy:

There is only a single letter difference between each pair of adjacent words. Every word si (1 <= I <= k) in the conversion process must be a word in the dictionary wordList. Note that beginWord does not have to be a word in the dictionary wordList. Sk == endWord gives you two words beginWord and endWord, as well as a dictionary wordList. Find and return all the shortest conversions from beginWord to endWord, or an empty list if none exist. Each sequence should be returned as a list of words [beginWord, S1, S2,… sk].

Answer key

My coding -_ – | | Error; Sad 😫 worthy of great difficulty.

const findLadders = (beginWord, endWord, wordList) => { let ans = []; const dict = new Set(wordList); // dictionary if(! dict.has(endWord)) return ans; // let q1 = [beginWord]; let q2 = [endWord]; const next = new Map(); let reversed = false, found = false; while(q1.length) { let q = []; while(q1.length){ let w = q1.shift(); for(let i = 0, len = w.length; i < len; i++) { for(let c = 97; c <= 122; c++){ const s = `${w.slice(0, i)}${String.fromCharCode(c)}${w.slice(i+1)}`; if(q2.includes(s)){ reversed? next.set(s, next.has(s) ? [... next.get(s), w]: [w]) : next.set(w, next.has(w) ? [... next.get(w), s]: [s]); found = true; } if(dict.has(s)) { reversed? next.set(s, next.has(s) ? [... next.get(s), w]: [w]) : next.set(w, next.has(w) ? [... next.get(w), s]: [s]); q.push(s); } } } } if(found) break; if(q.length <= q2.length) { q1 = q; } else { reversed = ! reversed; q1 = q2; q2 = q; } } if(found) { let path = [beginWord]; backtracking(beginWord, endWord, next, path, ans); } return ans; } function backtracking(src, dst, next, path, ans) { if(src === dst) { ans.push([...path]) } if(next.get(src)) { for(const s of next.get(src)) { path.push(s); backtracking(s, dst, next, path, ans); path.pop(); }}}Copy the code

Here is the explanation and the answer.

parsing

This problem uses three knowledge points, BFS, DFS backtracking. The first knowledge point is depth-first seACH (DFS). When a new node is found, the new node is traversed immediately. So traversal needs to be done with a first-in, last-out stack, or it can be done with a recursion equivalent to the stack. For a tree structure, it looks like it’s going “deep” because it’s always traversing new nodes. Depth-first search can also be used to detect loops by recording the parent nodes of each traversed node. If a node is traversed again and the parent nodes are different, a loop is present. Topological sorting can also be used to determine whether there is a loop. If the end is stored at a point where the entry degree is not zero, it indicates that there is a loop. Sometimes we may need to mark already searched nodes to prevent repeated searches of a node over time, a practice called state recording or memoization.

Second point.

Backtracking is a special case of priority search, also known as heuristic method, which is often used in depth-first search where nodal states need to be recorded. Generally speaking, it is convenient to use backtracking method for permutation, combination and selection problems.

As the name implies, the core of backtracking is backtracking. When searching for a node, if we find that the current node (and its children) is not the demand target, we can go back to the original node to continue searching and restore the modified state of the current node. The advantage of this is that we can always modify only the overall state of the graph, rather than creating a new graph to store the state each time we traverse. In terms of the specific writing, it is the same as the common depth-first search, which has the steps of [modify the current node state]→[recursive sub-node], but with more backtracking steps, it becomes [modify the current node state]→[recursive sub-node]→[change the current node state].

Two tips to remember are to pass the state by reference and to revert all state changes after the recursion is complete. There are generally two cases of backtracking modification. One is to modify the last bit of output, such as permutation and combination; One is to modify the access notation, such as the search string in the matrix.

The third point. Breadth first search (BFS) is different from depth-first search, which is traversed layer by layer, so it needs to traverse with first-in, first-out queue instead of first-in, last-out stack. Because it traverses by hierarchy, breadth-first search traverses in the direction of “wide”, and is often used to deal with problems such as shortest paths.

Both depth-first search and breadth-first search can deal with the issue of accessibility, that is, whether starting from one node can reach the other node. Because depth-first searches can be implemented quickly using recursion, many people are used to using depth-first search brushes. Stack overflow may occur; There is not much difference between stack depth-first search and queue breadth-first search, so which search method to use needs to be determined according to the actual functional requirements.

So let’s go back to our problem.

We can think of the start string, the end string, and all the strings in the word list as nodes. If two character strings differ by only one character, they are connected. Since the problem needs to output all of the modifications that have the least number of modifications, we can use breadth-first search to find the shortest distance from the start node to the end node.

At the end of the search, we also need to reconstruct all possible paths by backtracking.

1. The difference between two words with only one letter is an adjacency relationship, a progressive hierarchical relationship, and the shortest path relationship with the least number of output modifications.

All we need to do is, with BFS, build these wordlists into undirected graphs from the start node to other nodes, with neighboring nodes one character apart. If you layer these wordlists, each node records a level, one character apart, one level apart, which is a directed graph from the start character to the end character (the end character level is not necessarily the deepest level).

All possible paths from the start node to the final node are traced back through DFS.

2. State information required to construct BFS (Hierarchy) diagrams.

  • WordMap: Records all nodes, each node holds all its parent information, i.e. each node’s key is the current node information, the value is “fathers” array, records which words have changed.
  • LevelMap: Record the level of this word and select the level that meets the shortest path based on the number of levels of the fathers of the current node.
  • Note down the word visited to avoid adding it to the path repeatedly
  • Queue: a queue of words at each level, initially placed with the starting word,
  • We build this relationship at BFS for use at DFS.

3. BFS step

  • Find new words:The words traversing the current layer are listed one by oneChange the letters from a to Z to find new words in the word list.
  • WordMap stores new words that meet the criteria: as a key to wordMap, the value is its “parent word,” that is, the listed word.
  • Determine if the new word is the end word: If the new word happens to be the end word, there must be a path to the end word.
  • State and new 1-visited: Use the visited table to record the visited words and avoid adding them to the path repeatedly
  • Status update 2-levelMap: Record the level of the word on the path with levelMap.
  • Status update 3-queue: Queue new words from the next layer. Next loop is full of words from the next layer
  • The hierarchy state, access state, and words in each layer queue are unique, and only state records 1 and 23 can be updated.

coding

/ * * *@param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {string[][]}* /
const findLadders = (beginWord, endWord, wordList) = > {
   // create a status record table
   const wordSet = new Set(wordList);
   const ans = [];
   if(! wordSet.has(endWord))return ans; // There is no end word in the word list, return an empty array
   
   const wordMap = new Map(a);const levelMap = new Map(a);const visited = new Set(a);// Initialization state
   visited.add(beginWord)
   const queue = [beginWord];
   let finished = false;
   let level = 0;
   levelMap.set(beginWord, 0);
   
   / / BFS operation
   while(queue.length) {
     level++;
     for(let i = 0, levelSize = queue.length; i < levelSize; i++) {
       const word = queue.shift();
       for(let j = 0, len = word.length; j < len; j++) { // Iterate over all the characters of the word
         for(let c = 97; c <= 122; c++) { // Iterate over 26 alphabetic characters
           const newWord = `${word.slice(0, j)}The ${String.fromCharCode(c)}${word.slice(j+1)}`;
           if(! wordSet.has(newWord))continue; / Ignore words that are not in the word list// Store new words
           if(wordMap.has(newWord))
             wordMap.get(newWord).push(word);
            else 
             wordMap.set(newWord, [word]);
            if(visited.has(newWord)) continue; // The level state, the access state, and the words in each layer queue are unique, and the new word is ignored as it has already been accessed
            if(newWord === endWord)
              finished = true; levelMap.set(newWord, level); queue.push(newWord); visited.add(newWord); }}}}if(! finished)return ans;
  
  // DFS backtracks to find the path that matches the condition
  const dfs = (path, beginWord, word) = > {
    if(word === beginWord) {  // Find a path that is the same as the start word
       ans.push([beginWord, ...path]);
       return;
    }
    path.unshift(word); // DFS modifies the state to add the current word to the beginning of the path array
    if(wordMap.get(word)){
      for(const parent of wordMap.get(word)) { // Walk through the "parent words"
      if(levelMap.get(parent) + 1 === levelMap.get(word)) { 
      // A word may have many "neighbor words" to choose from, but in order to make the path shortest,
      // Select the node whose current word layer == neighbor word layer + 1. This is the node in the shortest path
        dfs(path, beginWord, parent);
      }
      }
    }
    path.shift(); // DFS regress status backtracking, undo selection, and pop up the word at the beginning of the path array
  }
   dfs([], beginWord, endWord);
   return ans;

}



Copy the code