Short DFS solution in python


  • 0
    Y
    class Solution(object):
        def dfs(self, grid, i, j):
            stack = [(i,j)]
            while stack:
                i,j = stack.pop()
                grid[i][j] = 0
                if i > 0 and grid[i-1][j] == "1":
                    stack.append((i-1, j))
                if j > 0 and grid[i][j-1] == "1":
                    stack.append((i, j-1))
                if i < len(grid) - 1 and grid[i+1][j] == "1":
                    stack.append((i+1, j))
                if j < len(grid[0]) - 1 and grid[i][j+1] == "1":
                    stack.append((i, j+1))
            
        def numIslands(self, grid):
            islands = 0
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == "1":
                        self.dfs(grid, i, j)
                        islands += 1
            return islands

  • 0

    This isn't DFS? The conventional iterative DFS uses a visited set and does not pop off of the stack before reaching a leaf "node" and working its way back up towards the root looking for more leaves on its way back up. This looks a lot more like a BFS solution. Just saying.


  • 0
    Y

    Visited set is not needed here because 1s are turned into 0s when visited.
    As for the stack, how does it reach the leaf without using recursion or stack? Can you show a "conventional" iterative DFS implementation?


Log in to reply
 

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