127 单词接龙

题目描述#

字典 wordList 中从单词 beginWord 到 endWord 的转换序列是一个序列 beginWord -> s1 -> s2 -> ... -> sk，其中：

每一对相邻单词只差一个字母
对于 1 <= i <= k，每个 si 都在 wordList 中（注意 beginWord 不必在 wordList 中）
sk == endWord

返回从 beginWord 到 endWord 的最短转换序列中的单词数目；如果不存在这样的转换，返回 0。

思路#

把每个单词看成图中的一个节点，两个单词若仅相差一个字母则连一条无向边。问题就是在这张无权图上求 beginWord 到 endWord 的最短路径长度——典型的 BFS。

不需要预先建图，扩展邻居时按位枚举就行：对当前单词的每一位依次替换为 'a' 到 'z' 中其余 25 个字母，得到的候选若在 wordList 中且未访问过就入队。这种做法对每个节点只产生 len(word) × 25 个邻居，比两两比较单词差异要快得多——拜托，谁会用 O(N²) 找邻居嘛～

层序 BFS 保证「第一次到达 endWord 就是最短距离」。这里有个返回值的小细节：题目要的是单词数目而不是变化次数，所以从起点 beginWord 算起就是 1 个单词，每展开一层 ans++ 自然代表「已经走了 ans 个单词」；当邻居生成时发现下一个就是 endWord，返回的应是 ans + 1，因为终点是下一层的节点。预先判断 endWord 不在 bank 中可以快速剪掉无解情况。

知识边界#

字符串"差一字符"问题（433 最小基因变化同款套路）：状态空间有限时，不建图、按位枚举邻居比预先建图更省事
返回的是「单词数目」而非「变化次数」，比 433 多 1：终点在邻居生成时命中要返回 ans + 1，这点容易写错
visited 必须在入队时打上而非出队时，否则同一节点会被多个父节点重复入队
beginWord 不要求在 wordList 中，但 endWord 必须在；否则不可能走通

代码#

func ladderLength(beginWord string, endWord string, wordList []string) int {
    bank := make(map[string]bool)
    for _, v := range wordList {
        bank[v] = true
    }
    if bank[endWord] == false {
        return 0
    }

    // BFS的准备
    visited := make(map[string]bool)
    queue := []string{beginWord}
    ans := 0

    for len(queue) > 0 {
        ans++
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[i]
            for j := 0; j < len(cur); j++ {
                for c := byte('a'); c <= 'z'; c++ {
                    if c == cur[j] {
                        continue
                    }
                    nextBytes := []byte(cur)
                    nextBytes[j] = c
                    next := string(nextBytes)

                    if next == endWord {
                        // endWord是下一层需要 + 1
                        return ans + 1
                    }

                    if bank[next] && visited[next] == false {
                        visited[next] = true
                        queue = append(queue, next)
                    }
                }
            }
        }
        queue = queue[size:]
    }
    return 0
}