LeetCode #752: Open the Lock, BFS Over Wheel States

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: a lock has 4 wheels and starts at 0000. Each move turns one wheel by one step. Return the fewest moves needed to reach the target without landing on a deadend, or −1 if that's impossible. Brute force: a DFS through all combinations finds some route, but not necessarily the shortest one. The key insight: each of the 10⁴ combinations is a node in a graph, and each node has 8 neighbours. A BFS finds the fewest moves. Put the deadends in the visited set from the start. If 0000 is a deadend, return −1 right away. Process the BFS level by level, and the level where the target shows up is the answer. A two-way BFS cuts the work further. Dry run: with target 0202 and 5 deadends, the shortest route takes 6 turns. Complexity: O(10⁴ · 8) time and O(10⁴) space. Problem: https://leetcode.com/problems/open-th... Related: Word Ladder (127), Minimum Genetic Mutation (433), Sliding Puzzle (773) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode752 #openthelock #bfs #graph #shortestpath #hashset #string #medium #coding #codinginterview #dsa #python #google #brutetobest