# 1. read the length and width
if len(grid) == 0:
return 0
(m,n) = (len(grid),len(grid[0]))
if (m == 0) or (n == 0):
return 0
# 2. Create a Visit matrix for checking
visit = [[False for j in range(n)] for i in range(m)]
count_island = 0
def check(x, y):
if x >=0 and x <m and y>=0 and y <n and visit[x][y] == False and grid[x][y] == "1":
return True
def bfs(x,y):
# move to up, down, right, left
moves = [(0,1),(0,1),(1,0),(1,0)]
q = [(x,y)]
while q:
x = q[0][0]
y = q[0][1]
q.pop(0)
for dx, dy in moves:
newx = x + dx
newy = y + dy
if check(newx, newy):
visit[newx][newy] = True
q.append((newx,newy))
# 3. for loop for each components
for row in range(m):
for col in range(n):
# 3.1 Check it is in the Matrix
if check (row, col):
# 3.2 Mark as visit for saving time
visit[row][col] = True
# 3.3 BFS for each node
bfs(row,col)
# 3.4 count +=1
count_island += 1
return count_island
CHUNCHIEH TSAI
@ChunChiehTsai
ChunChieh is a passionate data analyst with engineering background. He devoted himself to apply statistical modeling and AI in business area. He has more than 2 years of data science beginning in Microsoft as R&D intern to NYU as a graduate researcher in focusing on data visualization and Machine Learning applications.
LinkedIn : https://www.linkedin.com/in/chunchiehtsai
GitHub : https://github.com/DishT
0
Reputation
3
Posts
92
Profile views
0
Followers
0
Following
Posts made by ChunChiehTsai

Python BFS

Python BFS by ChunChieh Tsai
if not root: return [] # 1. Create a Queue to store q = [root] result = [] # 2. While loop to search each layer while q: new_q = [] result.append([node.val for node in q]) # 3. for loop to catch each head for node in q: if node.left: new_q.append(node.left) if node.right: new_q.append(node.right) q = new_q # 4. return result return result

Solution in Python
class Solution(object): def isValid(self, s): if len(s) % 2 != 0: return False #STEP 1. sign_map = {"(":")","[":"]","{":"}"} left = ["(","[","{"] right = [")","]","}"] l = [] #STEP 2. flag = False if s[0] in right: return False for item in s: if item in left: l.append(item) else: if sign_map[l.pop()] == item: flag = True else: return False if len(l) != 0: return False return flag