17.22. Word Transformer

Description

Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary.

Write code to return a possible transforming sequence. If there are more that one sequence, any one is ok.

Example 1:

Input:

beginWord = "hit",

endWord = "cog",

wordList = ["hot","dot","dog","lot","log","cog"]



Output:

["hit","hot","dot","lot","log","cog"]

Example 2:

Input:

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]



Output: []



Explanation: endWord "cog" is not in the dictionary, so there's no possible transforming sequence.

Solutions

Solution 1: DFS

We define an answer array ans, initially containing only beginWord. Then we define an array vis to mark whether the words in wordList have been visited.

Next, we design a function dfs(s), which represents whether we can successfully convert s to endWord starting from s. If successful, return True, otherwise return False.

The specific implementation of the function dfs(s) is as follows:

1. If s equals endWord, the conversion is successful, return True;
2. Otherwise, we traverse each word t in wordList. If t has not been visited and there is only one different character between s and t, then we mark t as visited, add t to ans, and then recursively call dfs(t). If True is returned, the conversion is successful, we return True, otherwise we remove t from ans and continue to traverse the next word;
3. If all the words in wordList have been traversed and no convertible word is found, the conversion fails, we return False.

Finally, we call dfs(beginWord). If True is returned, the conversion is successful, we return ans, otherwise return an empty array.

Python3JavaC++GoTypeScriptSwift

class Solution:
    de