Leetcode-127 Word Ladder

描述

https://leetcode.com/problems/word-ladder/

给定两个单词 beginWord ，endWord 和一组单词列表，求从 beginWord 到 endWord 的最短转换序列的长度，其中转换规则如下：

1. 每次只能转换一个字母
2. 每次转换后的单词都必须在给定的单词列表中

分析

如下案例,

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

首先使用（给定的单词和单词列表中的）每个单词作为一个顶点，构建连通图，如果两个顶点之间只相差一个字母，则两点之间可达。作图如下，

显然，问题的本质在于图的搜索，即从 beginWord 起始搜索 endWord，如果找到，返回最小路径，否则返回 0。那么问题分两部：

1. 构建无向图
2. 搜索

求解

1. 列表构建无向图，使用二维 map。其中两个顶点的连通性有他们之间的字母差异数决定，当且仅当两顶点的单词相差 1 个字母时连通。

   grahp = []
   wordList.append(beginWord)
   for x in wordList:
     if x not in graph:
       grahp[x] = {}
   	for y in wordList:
       	grahp[x][y] = acessiable(x, y)

   其中 accessiable 函数如下定义：

   def acessiable(a, b):
     if len(a) != len(b):
       return False
     i, diff = 0, 0
     while i < len(a):
       if a[i] != b[i]:
         diff += 1
         i += 1
   
         return diff == 1