ac solution code

• The basic idea is:

1. BFS: Find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node's next level neighbors to HashMap;
2. DFS: Output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distances of the current node + 1.
(Permutations)
P.S. BFS can only find one path of shortest length, DFS can get all permutations.

time = O(m!) - m is the crossing nodes with shortest path(all crossing nodes' neighbors when reach shortest path from start to end);
space = O(n)

``````func findLadders(_ start: String, _ end: String, _ wordList: [String]) -> [[String]] {
var res = [[String]]()
var wordList = Set<String>(wordList)// Convert ArrayList to HashSet
var nodeNeighbors = [String: [String]]()// Neighbors for every node
var distances = [String: Int]()// [node: distanceFromStartNode]
var path = [String]()

wordList.insert(start)// <-- start is not in wordList: need to add manually

// 1. Use BFS to find the shortest distances between start and end, tracing the distances of crossing nodes from start node to end node, and store node's next level neighbors to HashMap
BFS(start, end, &wordList, &nodeNeighbors, &distances)
// 2. Use DFS to output paths with the same distances as the shortest distances from distances HashMap: compare if the distances of the next level node equals the distances of the current node + 1
DFS(start, end, &wordList, nodeNeighbors, distances, &path, &res)
return res
}

// BFS: Trace every node's distances from the start node (level by level).
private func BFS(_ start: String, _ end: String, _ wordList: inout Set<String>, _ nodeNeighbors: inout [String: [String]], _ distances: inout [String: Int]) {
for str in wordList {
nodeNeighbors[str] = [String]()
}
var queue = Queue<String>()

queue.offer(start)// Start element
distances[start] = 0
while !queue.isEmpty {
let count = queue.size
var foundEnd = false
for i in 0 ..< count {
let curr =  queue.poll()!
let currdistances = distances[curr] ?? 0
let neighbors = getNeighbors(curr, wordList)

for neighbor in neighbors {
nodeNeighbors[curr]!.append(neighbor)
if !distances.keys.contains(neighbor) {// Check if visited
distances[neighbor] = currdistances + 1
if end == neighbor {// Found the shortest path
foundEnd = true// Found endWord
} else {
queue.offer(neighbor)
}
}
}
}
if foundEnd {
break
}
}
}

// Find all next level nodes.
private func getNeighbors(_ node: String, _ wordList: Set<String>) -> [String] {
var res = [String]()
var chs = [Character](node.characters)

let aUnicodeValue = Int(("a" as UnicodeScalar).value)
for c in 0 ..< 26 {// replace chs[i] with "a"..."z"
let ch = Character(UnicodeScalar(aUnicodeValue + c)!)
for i in 0 ..< chs.count {
if chs[i] == ch {
continue
}
let oldCh = chs[i]
chs[i] = ch // BFS: replace chs[i] with "a"..."z" (exclude chs[i])
if wordList.contains(String(chs)) {// <-- Only check nodes in wordList(wordList)
res.append(String(chs))
}
chs[i] = oldCh//Recover: backtracking
}
}
return res
}

// DFS: output all paths with the shortest distances.
private func DFS(_ curr: String, _ end: String, _ wordList: inout Set<String>,
_ nodeNeighbors: [String: [String]], _ distances:[String: Int], _ path: inout [String], _ res: inout [[String]]) {

path.append(curr)
if end == curr {// Termination case: Found one path
res.append(path)// Append one path
} else {
for neighbor in nodeNeighbors[curr]! {// Check out curr's neighbors to get next node of path
let currDistance = distances[curr] ?? 0// Curr's distance from start
if distances[neighbor] == currDistance + 1 {// Loop through neighbors, choose whose distance from start = currDistance + 1 as next, keep DFS
DFS(neighbor, end, &wordList, nodeNeighbors, distances, &path, &res)
}
}
}
path.removeLast()// Backtrack
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.