752.open-the-lock.md

752. Open the Lock

BFS

We can model this problem as a graph, the state of the 4 wheels is a node, each move of a wheel is an edge, the entire graphy contains 0000 to 9999 nodes. The next state of the 4 wheels is the neighbor of the current node, each node has 8 neighbors: We can rotate forward (0 to 1) or backward (0 to 9) for each wheel.

       0000
|     |     |     |     |     |     |     |    
0001  0010  0100  1000  0009  0090  0900  9000
|     |     |     |     |     |     |     |    
... so on.

       5678
|     |     |     |     
5679  5687  5768  6578
|     |     |     |     
... so on.

And we want to find the shortest path from the initial state 0000 to the target avoiding all the deadends.

fun openLock(deadends: Array<String>, target: String): Int {
    val deadSet = deadends.toHashSet()
    val initial = "0000"
    // Edge case: if the initial state is a deadend, return -1
    if (initial in deadSet) return -1
    val queue = ArrayDeque<String>()
    val visited = HashSet<String>()

    queue.addLast(initial)
    visited.add(initial)
    var turns = 0
    while (queue.isNotEmpty()) {
        val size = queue.size
        repeat (size) {
            val state = queue.removeFirst()
            if (state == target) return turns
            
            val adjSet = findNextStates(state)
            for (adj in adjSet) {
                if (adj in visited) continue
                if (adj in deadSet) continue

                queue.addLast(adj)
                visited.add(adj)
            }
        }
        turns++
    }
    return -1
}

private fun findNextStates(state: String): HashSet<String> {
    val nextStates = HashSet<String>()
    val chars = state.toCharArray()
    
    for (i in 0 until state.length) {
        val digit = chars[i] - '0'

        // rotate forward
        chars[i] = '0' + ((digit + 1) % 10)
        nextStates.add(String(chars))

        // rotate backward
        chars[i] = '0' + ((digit + 9) % 10)
        nextStates.add(String(chars))
        
        // restore the original digit
        chars[i] = '0' + digit
    }
    return nextStates
}

• Time Complexity: O(N * R), where N is the number of states, R is the number of rotations for each wheel, which is 8.
• Space Complexity: O(N + D), where N is the number of states, D is the number of deadends.

Bidirectional BFS

We can use the same above idea and implement the bidirectional BFS (similar to 127. Word Ladder).

fun openLock(deadends: Array<String>, target: String): Int {
    val deadSet = deadends.toHashSet()
    val initial = "0000"
    if (initial in deadSet) return -1
    if (target in deadSet) return -1
    val beginQueue = ArrayDeque<String>()
    val endQueue = ArrayDeque<String>()
    val beginVisited = HashSet<String>()
    val endVisited = HashSet<String>()

    beginQueue.addLast(initial)
    beginVisited.add(initial)

    endQueue.addLast(target)
    endVisited.add(target)
    var turns = 0
    while (beginQueue.isNotEmpty() && endQueue.isNotEmpty()) {
        // We always expand the smaller queue to improve the performance
        if (beginQueue.size <= endQueue.size) {
            if (expand(beginQueue, beginVisited, endVisited, deadSet)) return turns
            turns++
        } else {
            if (expand(endQueue, endVisited, beginVisited, deadSet)) return turns
            turns++
        }
    }
    return -1
}

private fun expand(queue: ArrayDeque<String>, visited: HashSet<String>, anotherVisited: HashSet<String>, deadSet: HashSet<String>): Boolean {
    val size = queue.size
    repeat (size) {
        val state = queue.removeFirst()
        if (state in anotherVisited) return true

        val nextStates = findNextStates(state)
        for (next in nextStates) {
            if (next in visited) continue
            if (next in deadSet) continue
            queue.addLast(next)
            visited.add(next)
        }
    }
    return false
}

private fun findNextStates(...) { ... } // Same as above