Leetcode-127 Word Ladder

描述

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

给定两个单词 beginWordendWord 和一组单词列表,求从 beginWordendWord 的最短转换序列的长度,其中转换规则如下:

  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

本文标题:Leetcode-127 Word Ladder

文章作者:Pylon, Syncher

发布时间:2019年08月13日 - 08:08

最后更新:2023年03月11日 - 17:03

原始链接:https://0x400.com/fundamental/algorithm/lc-127-word-ladder/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。