Straightforward Python DFS solution w/Comments


  • 0
    R
    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            
            numIslands = 0;
            #loops through each cell and starts searching if the cell is land
            #every encounter with a land that is a 1 not a -1 is the start of new island
            #I use -1 to mark the land as seen
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    if grid[i][j] == "1":
                        self.search(grid, i,j)
                        numIslands += 1
            return numIslands
            
        def search(self, grid, i, j):
            
            #return if the current index is out of bounds
            if i < 0 or i >= len(grid) or j >= len(grid[i]) or j < 0:
                return
            #return if the current cell is not land
            if grid[i][j] != "1" :
                return
            
            #marking cell as seen
            grid[i][j] = "-1"
            
            #recursively search left, bottom, right, and top directions
            #--this will exhaustively search all the adjacent lands and mark them as seen
            self.search(grid, i - 1, j)
            self.search(grid, i, j - 1)
            self.search(grid, i + 1, j)
            self.search(grid, i, j + 1)
           
    

Log in to reply
 

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