BFS

Problem Statement A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that: Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists....

Problem Statement You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1....

Problem Statement Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1. Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]] BFS: Iterative from collections import deque class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: ROWS, COLS = len(mat), len(mat[0]) """ * we need to find the distance to the nearest 0 * we know that m >= n >= 1 ~ no need to check dims * add zeros to queue * we can change mat """ queue = deque() # Add locations of zero cells to queue with distance of 0 # T: O(N*M) # S: O(N*M) for r in range(ROWS): for c in range(COLS): if mat[r][c] == 0: # (row, col, distance) queue....