Loading... 这道题主要就是得先扫描建图，然后就可以通过bfs找到最短路径抵达，然后建图我们也不需要完全建，用个中间态的存储法即可，也就是把每一个单词的某一个字符改为通配符对应的候选项放在一个节点下，这样我们只需要遍历 $N*L^2$，而不需要遍历 $N^2*L$，节省了一定的时间复杂度，当然这样做相当于在BFS阶段的队列长度相对会变大，但总体来说还是节省了一定的时间复杂度，特别是在N比较大的情况下。 ```go func ladderLength(beginWord string, endWord string, wordList []string) int { L := len(beginWord) dict := make(map[string]struct{}) for _, w := range wordList { dict[w] = struct{}{} } if _, ok := dict[endWord]; !ok { return 0 } patterns := make(map[string][]string) build := func(w string) { for i := 0; i < L; i++ { p := w[:i] + "*" + w[i+1:] patterns[p] = append(patterns[p], w) } } for _, w := range wordList { build(w) } build(beginWord) type node struct { w string d int } q := []node{{w: beginWord, d: 1}} visited := map[string]struct{}{beginWord: {}} for len(q) != 0 { front := q[0] q = q[1:] w := front.w d := front.d for i := 0; i < L; i++ { p := w[:i] + "*" + w[i+1:] neighs := patterns[p] if len(neighs) == 0 { continue } // 候选模式不需要二次遍历，所以这里直接赋值为nil减少重复 patterns[p] = nil for _, next := range neighs { if next == endWord { return d+1 } if _, ok := visited[next]; ok { continue } visited[next] = struct{}{} q = append(q, node{w: next, d: d+1}) } } } return 0 } ``` Last modification：August 14, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
