My Recursive Python Solution, 92ms


  • 0
    H
    class Solution:
        # @param {character[][]} grid
        # @return {integer}
        def numIslands(self, grid):
            if not grid:
                return 0
            m = len(grid)
            n = len(grid[0])
            nlabel = 2
            for i in range(m):
                for j in range(n):
                    # if not labeled
                    if grid[i][j] == '1':
                        self.label(nlabel, grid, i, j, m, n)
                        nlabel += 1
            return nlabel - 2
            
        def label(self, nlabel, grid, i, j, m, n):
            grid[i][j] = nlabel
            # right
            if j+1 < n and grid[i][j+1] == '1':
                self.label(nlabel, grid, i, j+1, m, n)
            # left
            if j-1 > -1 and grid[i][j-1] == '1':
                self.label(nlabel, grid, i, j-1, m, n)
            # down
            if i+1 < m and grid[i+1][j] == '1':
                self.label(nlabel, grid, i+1, j, m, n)
            # up
            if i-1 > -1 and grid[i-1][j] == '1':
                self.label(nlabel, grid, i-1, j, m, n)

Log in to reply
 

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