给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

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

输出: 5

解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。
示例 2:

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

输出: 0

解释: endWord “cog” 不在字典中，所以无法进行转换。

解法一：BFS

这是一个图最短路径的搜索问题，最短路径搜索适合用BFS因为BFS的第一个解就是最短路径。每个单词是一个节点，其邻居为替换了任意一个字母且在wordList中的单词。注意是无向图，需要visited集合避免环路。

  1. class Solution:
  2.     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:    
  3.         st = set(wordList)
  4.         if endWord not in st:
  5.             return 0
  6.         m = len(beginWord)    
  7.         queue = collections.deque()        
  8.         queue.append(beginWord)
  9.         visited = set([beginWord])
  10.         step = 0
  11.         while queue:
  12.             step += 1
  13.             for k in range(len(queue)):
  14.                 cur = queue.popleft()
  15.                 if cur == endWord:
  16.                     return step
  17.                 for i in range(m):                
  18.                     for j in range(26):
  19.                         tmp = cur[:i] + chr(97 + j) + cur[i+1:]
  20.                         if tmp not in visited and tmp in st:
  21.                             queue.append(tmp)
  22.                             visited.add(tmp)
  23.         return 0

解法二：DFS

无向图的路径搜索也可以用DFS+回溯。虽然DFS和BFS的问题规模是一样的，但DFS需要找到所有路径之后才能知道最短路径，当wordList非常长时，有可能会有非常多的路径，因此这题用DFS会超时。

DFS可以用递归实现也可以用栈实现，都需要visited集合。

  1. class Solution:
  2.     def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:    
  3.         def dfs(word, endWord, letters, st, visited, path):
  4.             nonlocal ans
  5.             if word == endWord:
  6.                 ans = min(ans, len(path))
  7.                 return
  8.             for i, chars in enumerate(letters):
  9.                 for char in chars:
  10.                     tmp = word[:i] + char + word[i+1:]
  11.                     if tmp not in visited and tmp in st:
  12.                         path.append(tmp)
  13.                         visited.add(tmp)
  14.                         dfs(tmp, endWord, letters, st, visited, path)
  15.                         path.pop()
  16.                         visited.remove(tmp)
  18.         letters = [set(chars) for chars in zip(*wordList)]
  19.         st = set(wordList)
  20.         ans = float('inf')
  21.         dfs(beginWord, endWord, letters, st, set(), [])
  22.         return ans + 1 if ans != float('inf') else 0