BFS time complexity : O(|E|) BFS space complexity : O(|V|)
do BFS from (0,0) of the grid and get the minimum number of steps needed to get to the lower right column
only step on the columns whose value is 1
if there is no path, it returns -1
def maze_search(grid):
dx = [0,0,-1,1]
dy = [-1,1,0,0]
n = len(grid)
m = len(grid[0])
q = [(0,0,0)]
visit = [[0]*m for _ in range(n)]
if grid[0][0] == 0:
return -1
visit[0][0] = 1
while q:
i, j, step = q.pop(0)
if i == n-1 and j == m-1:
return step
for k in range(4):
x = i + dx[k]
y = j + dy[k]
if x>=0 and x<n and y>=0 and y<m:
if grid[x][y] ==1 and visit[x][y] == 0:
visit[x][y] = 1
q.append((x,y,step+1))
return -1do BFS from each building, and decrement all empty place for every building visit when grid[i][j] == -b_nums, it means that grid[i][j] are already visited from all b_nums and use dist to record distances from b_nums
import collections
def shortest_distance(grid):
if not grid or not grid[0]:
return -1
matrix = [[[0,0] for i in range(len(grid[0]))] for j in range(len(grid))]
count = 0 # count how many building we have visited
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
bfs(grid, matrix, i, j, count)
count += 1
res = float('inf')
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j][1]==count:
res = min(res, matrix[i][j][0])
return res if res!=float('inf') else -1
def bfs(grid, matrix, i, j, count):
q = [(i, j, 0)]
while q:
i, j, step = q.pop(0)
for k, l in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
# only the position be visited by count times will append to queue
if 0<=k<len(grid) and 0<=l<len(grid[0]) and \
matrix[k][l][1]==count and grid[k][l]==0:
matrix[k][l][0] += step+1
matrix[k][l][1] = count+1
q.append((k, l, step+1))Given two words (begin_word and end_word), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time Each intermediate word must exist in the word list For example,
Given: begin_word = "hit" end_word = "cog" word_list = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. . Note: Return -1 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.
import unittest
def ladder_length(begin_word, end_word, word_list):
"""
Bidirectional BFS!!!
:type begin_word: str
:type end_word: str
:type word_list: Set[str]
:rtype: int
"""
if len(begin_word) != len(end_word):
return -1 # not possible
if begin_word == end_word:
return 0
# when only differ by 1 character
if sum(c1 != c2 for c1, c2 in zip(begin_word, end_word)) == 1:
return 1
begin_set = set()
end_set = set()
begin_set.add(begin_word)
end_set.add(end_word)
result = 2
while begin_set and end_set:
if len(begin_set) > len(end_set):
begin_set, end_set = end_set, begin_set
next_begin_set = set()
for word in begin_set:
for ladder_word in word_range(word):
if ladder_word in end_set:
return result
if ladder_word in word_list:
next_begin_set.add(ladder_word)
word_list.remove(ladder_word)
begin_set = next_begin_set
result += 1
# print(begin_set)
# print(result)
return -1
def word_range(word):
for ind in range(len(word)):
temp = word[ind]
for c in [chr(x) for x in range(ord('a'), ord('z') + 1)]:
if c != temp:
yield word[:ind] + c + word[ind + 1:]
class TestSuite(unittest.TestCase):
def test_ladder_length(self):
# hit -> hot -> dot -> dog -> cog
self.assertEqual(5, ladder_length('hit', 'cog', ["hot", "dot", "dog", "lot", "log"]))
# pick -> sick -> sink -> sank -> tank == 5
self.assertEqual(5, ladder_length('pick', 'tank',
['tock', 'tick', 'sank', 'sink', 'sick']))
# live -> life == 1, no matter what is the word_list.
self.assertEqual(1, ladder_length('live', 'life', ['hoho', 'luck']))
# 0 length from ate -> ate
self.assertEqual(0, ladder_length('ate', 'ate', []))
# not possible to reach !
self.assertEqual(-1, ladder_length('rahul', 'coder', ['blahh', 'blhah']))
if __name__ == '__main__':
unittest.main()