### BFS Template

```
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> visited; // store all the nodes that we've visited
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to visited;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to visited;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
```

### 133. Clone graph

Given a reference of a node in a

connectedundirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. class Node { public int val; public List neighbors; }

```
class Solution:
def cloneGraph(self, node): # BFS
if not node:
return node
m = {node: Node(node.val)}
deque = collections.deque([node])
while deque:
n = deque.popleft()
for neigh in n.neighbors:
if neigh not in m:
deque.append(neigh)
m[neigh] = Node(neigh.val)
m[n].neighbors.append(m[neigh])
return m[node]
```

### 752. open the lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot. The lock initially starts at ‘0000’, a string representing the state of the 4 wheels. You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it. Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:Input: deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202” Output: 6 Explanation: A sequence of valid moves would be “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”. Note that a sequence like “0000” -> “0001” -> “0002” -> “0102” -> “0202” would be invalid, because the wheels of the lock become stuck after the display becomes the dead end “0102”.Example 2:Input: deadends = [“8888”], target = “0009” Output: 1 Explanation: We can turn the last wheel in reverse to move from “0000” -> “0009”.

```
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if "0000" in deadends:
return -1
queue = collections.deque()
queue.append(('0000', 0))
visited = set('0000')
visited.update(deadends)
while queue:
string, step = queue.popleft()
if string == target:
return step
for i in range(4):
num = int(string[i])
for dx in (-1, 1):
num_new = (num + dx) % 10
string_new = string[:i] + str(num_new) + string[i+1:]
if string_new not in visited:
queue.append((string_new, step+1))
visited.add(string_new)
return -1
```

```
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if "0000" in deadends:
return -1
step = -1
q = collections.deque(["0000"])
visited = set("0000")
visited.update(deadends)
def findNeighbor(node):
neighbors = []
for i,v in enumerate(node):
if v == "0":
l, r = "9", "1"
elif v == "9":
l, r = "8", "0"
else:
l, r = str(int(v)-1), str(int(v)+1)
neighbors.append(node[:i] + l + node[i+1:])
neighbors.append(node[:i] + r + node[i+1:])
return neighbors
while q:
step += 1
cur_q_size = len(q)
while cur_q_size:
cur_q_size -= 1
cur = q.popleft()
if cur == target:
return step
neighbors = findNeighbor(cur)
for neighbor in neighbors:
if neighbor not in visited:
q.append(neighbor)
visited.add(neighbor)
return -1
```

### 279. Perfect squares

Given an integer n, return

the least number of perfect square numbers that sum ton. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.

Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.

```
class Solution(object):
def numSquares(self, n):
candidates = collections.deque([0])
visited = set()
potential = [i*i for i in range(1, int(n**0.5) + 1)]
step = 0
while candidates:
step += 1
sz = len(candidates)
for _ in range(sz):
cur = candidates.popleft()
for v in potential:
if v + cur < n and v + cur not in visited:
candidates.append(v + cur)
visited.add(v + cur)
elif v + cur == n:
return step
```

### 733. Flood fill

CompaniesAn image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform aflood fillon the image starting from the pixel image[sr][sc].

To perform aflood fill, consider the starting pixel, plus any pixels connected4-directionallyto the starting pixel of the same color as the starting pixel, plus any pixels connected4-directionallyto those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor. Returnthe modified image after performing the flood fill.

```
class Solution:
def floodFill(self, image, sr, sc, newColor):
old, m, n = image[sr][sc], len(image), len(image[0])
if old != newColor:
q = collections.deque([(sr, sc)])
while q:
i, j = q.popleft()
image[i][j] = newColor
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < m and 0 <= y < n and image[x][y] == old:
q.append((x, y))
return image
```

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.

Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Example 2: Input: coins = [2], amount = 3Output: -1

```
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0: return 0
visited = set()
potential = collections.deque(coins)
visited.update(coins)
step = 0
while potential:
step += 1
for _ in range(len(potential)):
if potential[0] == amount:
return step
for c in coins:
if c + potential[0] not in visited:
potential.append(c + potential[0])
visited.add(c + potential[0])
potential.popleft()
if all(p > amount for p in potential):
break
return -1
```

```
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if amount == 0: return 0
queue = [[0, 0]]
visited = {0}
step = 0
for node, step in queue:
for coin in coins:
if node + coin == amount: return step + 1
elif node + coin < amount and node + coin not in visited:
queue.append([node + coin, step + 1])
visited.add(node + coin)
return -1
```

### 542. 01-matrix

Given an m x n binary matrix mat, return

the distance of the nearest. The distance between two adjacent cells is 1.0for each cellExample 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]]

```
class Solution:
def updateMatrix(self, matrix):
rows_len, cols_len = len(matrix), len(matrix[0])
start_0 = [(x,y) for x in range(rows_len) for y in range(cols_len) if matrix[x][y] == 0]
visited = set()
q = deque(start_0)
visited.update(start_0)
# result = [[-1 for _ in range(cols_len)] for y in range(rows_len)]
while q:
for _ in range(len(q)):
x, y = q.popleft()
for d in [[0,1],[0,-1],[1,0],[-1,0]]:
m, n = x + d[0], y + d[1]
if 0 <= m < rows_len and 0 <= n < cols_len and (m,n) not in visited:
matrix[m][n] = matrix[x][y] + 1 # update matrix directly
q.append((m, n))
visited.add((m, n))
return matrix
```

### 127. Word ladder

A

transformation sequencefrom 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 == endWordGiven two words, beginWord and endWord, and a dictionary wordList, returnthebeginWordnumber of wordsin theshortest transformation sequencefromtoendWord__, or __0__ if no such sequence exists.__

**Example 1:**

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] Output: 5 Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog", which is 5 words long.

```
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
def construct_dict(word_list):
d = {}
for word in word_list:
for i in range(len(word)):
s = word[:i] + "_" + word[i+1:]
d[s] = d.get(s, []) + [word]
return d
def bfs_words(begin, end, dict_words):
queue, visited = deque([(begin, 1)]), set()
while queue:
word, steps = queue.popleft()
if word not in visited:
visited.add(word)
if word == end:
return steps
for i in range(len(word)):
s = word[:i] + "_" + word[i+1:]
neigh_words = dict_words.get(s, [])
for neigh in neigh_words:
if neigh not in visited:
queue.append((neigh, steps + 1))
return 0
d = construct_dict(set(wordList))
return bfs_words(beginWord, endWord, d)
```