面试题 17.22. 单词转换

给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。

编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
["hit","hot","dot","lot","log","cog"]

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

Python 解答：
1.回溯

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:
        isSelect = [False for i in range(len(wordList))]            
        path = []
        def check(first, second):
                if len(first) != len(second):
                    return False
                c, k = 0, 0
                while k < len(first):
                    if first[k] != second[k]:
                        c += 1
                    k += 1
                return c == 1
        def dfs(beginWord, endWord, res):
            if beginWord == endWord:
                nonlocal path
                path.append(res[::])
                return True
            else:
                for i in range(len(wordList)):
                    if isSelect[i] == False and check(beginWord, wordList[i]):
                        res.append(wordList[i])
                        isSelect[i] = True
                        flag = dfs(wordList[i], endWord, res)
                        if flag:
                            return True
                        res.pop()
                        # isSelect[wordList[i]] = False
                return False
        exist = dfs(beginWord, endWord, [beginWord])
        if exist:
            return path[0]
        else:
            return []