# Python iterative/recursive BFS/DFS

• I first used a "visited" set to store visited point, and then I found my old implementation set the visited point to "2", as posted. Then I was confused, isn't string immutable?

Problem solved: input are not list of strings.

``````def numIslands(self, grid):
# BFS
if not grid:
return 0
m, n, count = len(grid), len(grid[0]), 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
stack = [(i,j)]
for ii,jj in stack:
if 0<=ii<m and 0<=jj<n and grid[ii][jj] == "1":
grid[ii][jj] = "2"
stack.extend([(ii+1,jj),(ii-1,jj),(ii,jj-1),(ii,jj+1)])
return count

# DFS
if not grid:
return 0
m, n, count = len(grid), len(grid[0]), 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
stack = [(i,j)]
while stack:
ii, jj = stack.pop()
if 0<=ii<m and 0<=jj<n and grid[ii][jj] == "1":
grid[ii][jj] = "2"
stack.extend([(ii+1,jj),(ii-1,jj),(ii,jj-1),(ii,jj+1)])
return count

## recursive DFS
def dfs(grid, i,j):
if 0<=i<m and 0<=j<n and grid[i][j] == "1":
grid[i][j] = "2"
dfs(grid, i-1, j)
dfs(grid, i+1, j)
dfs(grid, i, j-1)
dfs(grid, i, j+1)
if not grid:
return 0
m, n, count = len(grid), len(grid[0]), 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
dfs(grid, i, j)
return count``````

• Yes, Python strings are immutable.

• Hey Stefan! Then why in this problem we are able to reset the string value?

• I guess you think the input is a list of strings? It's not. Print the grid to see what you actually get or check the signature specification and you'll see it's a list of lists of (single-character) strings.

• I see. Thank you for the answer! I updated the post.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.