Last updated
Was this helpful?
Last updated
Was this helpful?
Yes, definitely you can apply DFS here. As the whole search space is 10^4 = 10000, DFS can work here too. But why many people choose BFS instead? Because the problem here asks for the minimum number of steps to achieve the target state. Using BFS, we can report the answer as long as we reach the target state. But using DFS, we can't guarantee that the initial target state that we reach is the optimal solution. You still have to search the whole search space. Think about the problem that to find the depth of a binary tree, it is quite similar in this sense.
Time Complexity: O(N^2 A^N + D) where A is the number of digits in our alphabet, N* is the number of digits in the lock, and D is the size of deadends
. We might visit every lock combination, plus we need to instantiate our set dead
. When we visit every lock combination, we spend O(N^2) time enumerating through and constructing each node.
Space Complexity: O(A^N + D), for the queue
and the set dead
.