Leetcode-127 Word Ladder

Posted on Edited on In ,

描述

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

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

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

分析

如下案例,

1
2
3
4
5
6
7
8
9
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 个字母时连通。

    1
    2
    3
    4
    5
    6
    7
    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 函数如下定义：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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