Created
March 1, 2019 01:07
-
-
Save d8660091/c994d6f22b61842ab903f953934867d8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment