2021-09-07：单词接龙 II。按字典 wordList 完成从单词 beginWord 到单词 endW

2021-09-07：单词接龙 II。按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。sk == endWord，给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。力扣126。

福大大 答案2021-09-07：

递归。遍历找邻居。
时间复杂度：O(kN)和O(26k*k)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {

    beginWord := "hit"
    endWord := "cog"
    wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}
    ret := findLadders(beginWord, endWord, wordList)
    fmt.Println(ret)

}

func findLadders(start string, end string, list0 []string) [][]string {
    list0 = append(list0, start)
    nexts := getNexts(&list0)
    distances := getDistances(start, nexts)
    pathList := make([]string, 0)
    res := make([][]string, 0)
    getShortestPaths(start, end, nexts, distances, &pathList, &res)
    return res
}

//
func getNexts(words *[]string) map[string][]string {
    dict := make(map[string]struct{})
    for _, word := range *words {
        dict[word] = struct{}{}
    }
    nexts := make(map[string][]string)
    for i := 0; i < len(*words); i++ {
        nexts[(*words)[i]] = getNext((*words)[i], dict)
    }
    return nexts
}

// word, 在表中，有哪些邻居，把邻居们，生成list返回
func getNext(word string, dict map[string]struct{}) []string {
    res := make([]string, 0)
    chs := []byte(word)
    for cur := byte('a'); cur <= 'z'; cur++ {
        for i := 0; i < len(chs); i++ {
            if chs[i] != cur {
                tmp := chs[i]
                chs[i] = cur
                if _, ok := dict[fmt.Sprintf("%s", chs)]; ok {
                    res = append(res, fmt.Sprintf("%s", chs))
                }
                chs[i] = tmp
            }
        }
    }
    return res
}

// 生成距离表，从start开始，根据邻居表，宽度优先遍历，对于能够遇到的所有字符串，生成(字符串，距离)这条记录，放入距离表中
func getDistances(start string, nexts map[string][]string) map[string]int {

    distances := make(map[string]int)
    distances[start] = 0
    queue := make([]string, 0)
    queue = append(queue, start)
    set := make(map[string]struct{})
    set[start] = struct{}{}
    for len(queue) > 0 {
        //cur := queue[len(queue)-1]
        //queue = queue[0 : len(queue)-1]
        cur := queue[0]
        queue = queue[1:]
        for _, next := range nexts[cur] {
            if _, ok := set[next]; !ok {
                distances[next] = distances[cur] + 1
                queue = append(queue, next)
                set[next] = struct{}{}
            }
        }
    }
    return distances
}

// cur 当前来到的字符串 可变
// to 目标，固定参数
// nexts 每一个字符串的邻居表
// cur 到开头距离5 -> 到开头距离是6的支路 distances距离表
// path : 来到cur之前，深度优先遍历之前的历史是什么
// res : 当遇到cur，把历史，放入res，作为一个结果
func getShortestPaths(cur string, to string, nexts map[string][]string, distances map[string]int, path *[]string, res *[][]string) {
    *path = append(*path, cur)
    if to == cur {
        //res.add(new LinkedList<String>(path));
        pathcopy := make([]string, len(*path))
        copy(pathcopy, *path)
        *res = append(*res, pathcopy)
    } else {
        for _, next := range nexts[cur] {
            if distances[next] == distances[cur]+1 {
                getShortestPaths(next, to, nexts, distances, path, res)
            }
        }
    }
    //path.pollLast();
    *path = (*path)[0 : len(*path)-1]
}

执行结果如下：

左神java代码