Broad First Search

Sliding Puzzle (Leetcode 773)

We can think of this problem as a graph traversal problem, where each state is a configuration of the puzzle, and the neighbors of a state are the configurations that can be reached by sliding a tile.

from collections import deque

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # Decompose the 2D list into 1D string

        start_state = "".join(str(x) for row in board for x in row)
        target = "123450"

        neighbor_map = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }

        queue = deque()
        queue.append((start_state, 0))
        visited = set()
        visited.add(start_state)

        while queue:
            state, step = queue.popleft()

            if state == target:
                return step

            # Let us find the zero index
            zero_idx = state.index('0')

            for neighbor_idx in neighbor_map[zero_idx]:
                state_list = list(state)

                state_list[zero_idx], state_list[neighbor_idx] = state_list[neighbor_idx], state_list[zero_idx]

                new_state = "".join(state_list)

                if new_state not in visited:
                    visited.add(new_state)

                    queue.append((new_state, step+1))

        return -1

Open the Lock (Leetcode 752)

from collections import deque
class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        start = '0000'

        if target == start:
            return 0

        def getNeighbors(state):
            res = []
            for i in range(4):
                x = int(state[i])
                for d in (-1, 1):
                    y = (x + d) % 10 
                    new_state = state[:i] + str(y) + state[i+1:]
                    res.append(new_state)
            return res

        visited = set(deadends)
        queue = deque()

        if start in visited:
            return -1



        queue.append(('0000', 0))
        visited.add('0000')


        while queue:
            state, step = queue.popleft()

            if state == target:
                return step

            for neighbor in getNeighbors(state):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, step + 1))

        return -1

Word Ladder (Leetcode 127)

from collections import deque
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        n = len(beginWord)
        ALPHABET = "abcdefghijklmnopqrstuvwxyz"

        if len(endWord) != len(beginWord) or (not wordList) or endWord not in wordList:
            return 0

        q = deque()
        visited = set()
        wordset = set(wordList)

        q.append((beginWord, 1))
        visited.add(beginWord)

        while q:
            word, depth = q.popleft()

            char_list = list(word)
            for i in range(n):
                for char_new in list(ALPHABET):
                    if char_list[i] == char_new :
                        continue

                    word_new = char_list[:]
                    word_new[i] = char_new
                    word_new = "".join(word_new)

                    if word_new == endWord:
                        return depth + 1

                    if word_new in wordset and word_new not in visited:
                        q.append((word_new, depth + 1))
                        visited.add(word_new)

        return 0