ac solution code


  • 0

    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)

    Inspired by:
    http://www.jiuzhang.com/paths/word-ladder-ii/
    http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/

    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
        }
    

    0_1486451280293_Evernote_Camera_Roll_20170206_225227.jpg


Log in to reply
 

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