esc to dismiss

127. 单词接龙

题目

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列:

  • 序列中第一个单词是 beginWord 。

  • 序列中最后一个单词是 endWord 。

  • 每次转换只能改变一个字母。

  • 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ,找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0。

示例 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 本身,而是在 建图,即如何建立起单词间的转换关系。单词间只能有一个字母不一样,因此,如果用暴力枚举每一种组合的话,效率很低,时间复杂度是 O(n^2).

因此,题解中给了优化建图思路:使用 虚拟节点来辅助建图:

具体地,我们可以创建虚拟节点。对于单词 hit,我们创建三个虚拟节点 *it、h*t、hi*,并让 hit 向这三个虚拟节点分别连一条边即可。如果一个单词能够转化为 hit,那么该单词必然会连接到这三个虚拟节点之一。对于每一个单词,我们枚举它连接到的虚拟节点,把该单词对应的 id 与这些虚拟节点对应的 id 相连即可。

而后,去掉这些虚拟节点,实际的关系图就建立起来了。

我的代码:

func matchedVirualNode(word, other string, index int) bool {
    size := len(word)
    for i := 0; i < size; i++ {
        if i != index && word[i] != other[i] {
            return false
        }
    }
    return true
}

func linkGraph(wordList []string, start, size int, graph [][]int) {
    wordSize := len(wordList[start])
    for i := 0; i < wordSize; i++ {
        var similars []int
        for j := start + 1; j < size; j++ {
            if matchedVirualNode(wordList[start], wordList[j], i) {
                similars = append(similars, j)
            }
        }
        if len(similars) > 0 {
            similars = append(similars, start)
        }

        for _, m := range similars {
            for _, n := range similars {
                if m != n {
                    graph[m][n] = 1
                }
            }
        }
    }
}

func buildGraph(wordList []string) [][]int {
    size := len(wordList)
    graph := make([][]int, size, size)
    for i := 0; i < size; i++ {
        graph[i] = make([]int, size, size)
    }

    for i := 0; i < size-1; i++ {
        linkGraph(wordList, i, size, graph)
    }
    return graph
}

func ladderLength(beginWord string, endWord string, wordList []string) int {
    var graph [][]int
    wordMap := make(map[string]int)
    for i := 0; i < len(wordList); i++ {
        wordMap[wordList[i]] = i
    }
    endIndex, ok := wordMap[endWord]
    if !ok {
        return 0
    }

    fullWordList := append(wordList, beginWord)
    graph = buildGraph(fullWordList)
    beginIndex := len(fullWordList) - 1

    searched := make(map[int]int)
    size := len(graph)
    candidates := []int{endIndex}
    step := 1
    for len(candidates) > 0 {
        var newCandidates []int
        step++
        for _, c := range candidates {
            for i := 0; i < size; i++ {
                if graph[c][i] == 1 && searched[i] == 0 {
                    if beginIndex == i {
                        return step
                    }
                    newCandidates = append(newCandidates, i)
                    searched[i] = 1
                }
            }
        }
        candidates = newCandidates
    }

    return 0
}

经验教训

关于图的表示有邻接表 和 邻接矩阵两种方式,邻接表可用 hash map, 而邻接矩阵用二维数组,这道题用 邻接表 更合适。我在做题时用了邻接矩阵,逻辑复杂不说,效率还比邻接表差。

x