Python Simple DFS Solution


  • 27
    G

    Iterate through each of the cell and if it is an island, do dfs to mark all adjacent islands, then increase the counter by 1.

    def numIslands(self, grid):
        if not grid:
            return 0
            
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count
    
    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

  • 0
    G

    I have seen your codes several times, you can always come up with simple solution expressed with concise codes. Your are genius.


  • 0
    F

    when I finish my version, I open this topic·····

    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid:
                return 0
            res, grid = 0, [list(s) for s in grid]
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == '1':
                        res += 1
                        self.DFS(grid, i, j)
            return res
    
        def DFS(self, grid, i, j):
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':
                return
            if grid[i][j] == '1':
                grid[i][j] = '#'
                self.DFS(grid, i, j - 1)
                self.DFS(grid, i, j + 1)
                self.DFS(grid, i - 1, j)
                self.DFS(grid, i + 1, j)
    

    I found some stupid operation shouldn't be there when I compared your solution.


  • 0
    D

    I have a weird issue:
    in the DFS
    grid[i][j] = '#'

    it will report error in IDE, saying
    TypeError: 'str' object does not support item assignment

    After searching it says string are not mutable and cannot be changed like this.
    I'm wondering why it would pass in LeetCode OJ.


  • 0
    S

    easy understand! but slow


  • 0
    M

    Great solution. Simple and efficient.


Log in to reply
 

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