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

word-ladder-ii.go

func findLadders(beginWord string, endWord string, wordList []string) [][]string {
    
    path := make(map[string][][]string)
    
    queue := []string{beginWord}
    path[beginWord] = [][]string{{beginWord}}
    
    for len(queue) != 0 {
        u := queue[0]
        queue = queue[1:]
        
        for _, v := range wordList {
            _, vVisited := path[v]
            hasSameDepth := false
            if vVisited {
                if adjacent(u, v) && len(path[u][0]) == len(path[v][0]) - 1 {
                    hasSameDepth = true
                }
            }
           
        
            if adjacent(u, v) && (!vVisited || hasSameDepth) {
                if !vVisited {
                     queue = append(queue, v)
                }
               
                // u is the parent
                for _, p := range path[u] {
                    pp := append(cp(p), v)
                    path[v] = append(path[v], pp)
                    
                }
            }
        }
    }

    return path[endWord]
}

func adjacent(u, v string) bool {
    if len(u) != len(v) {
        return false
    }    
    
    count := 0
    for i := range u {
        if u[i] != v[i] {
            count++
        }
    }
    
    return count == 1
}

func cp(s []string) []string{
    ss := make([]string ,len(s))
    copy(ss, s)
    return ss
}