200.md

Number of Islands

Description

link

---

Solution

• See Code

---

Code

O(n)

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j, k):
            if grid[i][j] != "1":
                return
            grid[i][j] = str(k)
            if i > 0:
                dfs(i - 1, j, k)
            if j > 0:
                dfs(i, j - 1, k)
            if i < m - 1:
                dfs(i + 1, j, k)
            if j < n - 1:
                dfs(i, j + 1, k)
        
        num = 2
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    dfs(i, j, num)
                    num += 1
                    
        return len(set([i for row in grid for i in row if i != "0"]))