I was trying to solve this leetcode problem involving DFS with Python: https://leetcode.com/problems/count-sub-islands/
This is my initial solution, which failed the test cases:
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
ans=0
def dfs(i,j):
if not (0<=i<len(grid1) and 0<=j<len(grid1[0]) and grid2[i][j]):
return True
if (not grid2[i][j] and grid1[i][j]) or (grid2[i][j] and not grid1[i][j]):
return False
if grid1[i][j] and grid2[i][j]:
grid2[i][j] = 0
return dfs(i+1,j) and dfs(i-1,j) and dfs(i,j+1) and dfs(i,j-1)
for i in range(len(grid2)):
for j in range(len(grid2[0])):
if grid2[i][j] and dfs(i,j):
ans+=1
return ans
However, when I split up the dfs calls in the return statement like this, the code worked:
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
ans=0
def dfs(i,j):
if not (0<=i<len(grid1) and 0<=j<len(grid1[0]) and grid2[i][j]):
return True
if (not grid2[i][j] and grid1[i][j]) or (grid2[i][j] and not grid1[i][j]):
return False
if grid1[i][j] and grid2[i][j]:
grid2[i][j] = 0
#return dfs(i+1,j) and dfs(i-1,j) and dfs(i,j+1) and dfs(i,j-1)
one=dfs(i+1,j)
two=dfs(i-1,j)
three=dfs(i,j+1)
four=dfs(i,j-1)
return one and two and three and four
for i in range(len(grid2)):
for j in range(len(grid2[0])):
if grid2[i][j] and dfs(i,j):
ans+=1
return ans
Can someone explain to me the difference between the dfs calls, since they seem to be equivalent to me? Thank you!
I tried the first code snippet, which didn't work. After splitting up the dfs calls in the second snippet, it worked.
This is caused by and's "short-circuiting" behavior, where the expression is evaluated left to right until it encounters a False value, after which it will stop evaluating that expression. When you separated out each of the dfs calls, the short-circuiting behavior was bypassed because each dfs call was executed before the and expression. But in your first code, the short-circuiting behavior of and would cause some dfs calls to not be made, making your function incorrect.
For example, if it were to happen that dfs(i+1,j) returned a False value, then evaluation of the and expression will immediately stop there and dfs(i-1,j), dfs(i,j+1) and dfs(i,j-1) will not be called.