Im not sure how to explain this. Basically I am trying to do Leetcode problem “752. open the lock”

My solution was to use breadth first search algorithm. Basically:

1. Generate the 10,000 possible combination graph like so

graph{
0000:{0001,0010,0100,...9000},
.
.
.
9999:{9990,9909...0999}
}

2. use breadth first search to print out every single possible paths from start to end, save those paths into a 2d array.
3. as per the target and deadlocks start filtering every path

• take out all those paths with deadlocks
• take out all those paths where target is not the final value

4. get the length of the shortest path, minus 1 and then return it

When manually testing the testcases, it seems like my program works. But generating the 10,000 possible combinations took so long that when I submit, Leetcode gives time limit exceed error.

When using BFS, shouldn’t there be an existing graph? But when generating the graph it takes too long to compute. So how do I go about generating a graph during the BFS dynamically, which could shorten the time to compute

class Solution:
    @staticmethod
    def generate_lock_graph():
        # Initialize the lock graph
        lock_graph = {}
        
        # Generate all possible combinations of lock digits
        for i in range(10):
            for j in range(10):
                for k in range(10):
                    for l in range(10):
                        node = f"{i}{j}{k}{l}"  # Create a lock combination node
                        neighbors = []  # Initialize the list of neighboring nodes
                        
                        # Generate all possible moves for the current lock combination
                        for digit in range(4):
                            # Generate a new lock combination by incrementing the digit
                            new_combination = list(node)
                            new_combination[digit] = str((int(new_combination[digit]) + 1) % 10)
                            neighbors.append("".join(new_combination))
                            
                            # Generate a new lock combination by decrementing the digit
                            new_combination = list(node)
                            new_combination[digit] = str((int(new_combination[digit]) - 1) % 10)
                            neighbors.append("".join(new_combination))
                        
                        lock_graph[node] = neighbors
        
        return lock_graph

    @staticmethod
    def bfs(graph, start):
        global explored
        global queue
        global possiblePaths

        explored = []
        queue = [[start]]
        possiblePaths = [[start]]

        while queue:  # Creating loop to visit each node
            # Get current node
            path = queue.pop(0)
            node = path[-1]

            if node not in explored:
                neighbours = graph[node]
                for neighbour in neighbours:
                    new_path = list(path)
                    new_path.append(neighbour)

                    possiblePaths.append(new_path)
                    queue.append(new_path)
                explored.append(node)
        # print(possiblePaths)
        return possiblePaths

    def openLock(self, deadends: List[str], target: str) -> int:
        graph = self.generate_lock_graph() #generate the graph
        allpaths = self.bfs(graph,"0000") #start bfs, give all possible path from start to finish
        allpaths = [path for path in allpaths if not any(deadend in path for deadend in deadends)] # remove all paths with deadends
        # allpaths = [path for path in allpaths if target in path] # remove all paths without the target
        allpaths = [path for path in allpaths if path[-1] == target] # remove all paths where target is not the final value
        # print(allpaths)
        if len(allpaths) == 0: # return -1 if no possible paths
            return -1
        else:
            return len(allpaths[allpaths.index(min(allpaths,key=len))]) - 1 # minus one to remove the first node, get the shortest list (shortest path)
solution = Solution()
# solution.bfs(graph,'0000')
deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
print(solution.openLock(deadends,target))