LeetCode 200: Number of Islands

問題描述

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

限制條件

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

範例

• Example 1:
  Input: grid = [
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]
]
Output: 1
• Example 2:
  Input: grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
Output: 3

解法一：深度優先搜尋 (DFS)

解題思路

我們可以利用 DFS 的技巧對整個 grid 進行遍歷，每當遇到 land 時，將所有與之相連的其他 land 都做上標記（若題目不允許更改初始 grid，可利用一個 hash set 來做記錄）並持續統計總共遍歷過了幾個獨立的 island。

步驟詳解

1. 使用 DFS 技巧遍歷 grid 中的每個元素。若當前元素為 '1', 將 num_islands 遞增 1 後將當前座標作為輸入參數呼叫 dfs_helper。
2. 在 dfs_helper 中：
   1. 基本情況 (Base Case)：根據若當前座標超出 grid 的範圍，或是當前元素並非 '1'，中斷目前的呼叫。
   2. 若否，將目前元素標記為 '#' 代表已造訪過。
   3. 將與目前座標相鄰的四個座標作為參數分別遞迴式呼叫 dfs_helper。
3. 遍歷完成後回傳 num_islands。

程式碼

def num_islands(grid: List[List[str]]) -> int:
    m = len(grid)
    n = len(grid[0])
    num_islands = 0

    def dfs_helper(i: int, j: int) -> None:
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
            return

        grid[i][j] = '#'
        dfs_helper(i + 1, j)
        dfs_helper(i - 1, j)
        dfs_helper(i, j + 1)
        dfs_helper(i, j - 1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                num_islands += 1
                dfs_helper(i, j)

    return num_islands

複雜度分析

• 時間複雜度：O(MN)，其中 N 為 grid 的寬度，M 為 grid 的長度。
• 空間複雜度：O(MN)，其中 N 為 grid 的寬度，M 為 grid 的長度。

解法二：廣度優先搜尋 (BFS)

解題思路

類似於上述 DFS 的作法，我們同樣可以使用 BFS 來對整個 grid 進行遍歷。唯一不同的是我們不需要定義一個遞迴的輔助函式來延伸與當前 land 連接的所有其他 land，取而代之的是利用佇列 (queue) 向外擴展。使用 queue 來搭配實現 BFS 搜尋是相當經典的技巧。

步驟詳解

1. 使用 BFS 技巧遍歷 grid 中的每個元素：
   1. 若當前元素為非 '1'，跳過當次迭代。
   2. 若否，將 num_islands 遞增 1 後將當前座標 (i, j) 作為 queue 的初始出發點。
   3. 當 queue 內不為空時，持續將 queue 內的座標從首端移出。若移出的座標在 grid 的範圍內，且其對應元素為 '1'，將其標示為 '#'，並將與其相鄰的四個座標依序插入 queue 的末端。
2. 遍歷完成後，回傳 num_islands。

程式碼

def num_islands(grid: List[List[str]]) -> int:
    m = len(grid)
    n = len(grid[0])
    num_islands = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] != '1':
                continue

            num_islands += 1
            queue = [(i, j)]
            while queue:
                (x, y) = queue.pop()
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    grid[x][y] = '#'
                    queue += [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]

    return num_islands

複雜度分析

• 時間複雜度：O(MN)，其中 N 為 grid 的寬度，M 為 grid 的長度。
• 空間複雜度：O(MN)，其中 N 為 grid 的寬度，M 為 grid 的長度。

參考資料

• LeetCode 原題出處：Number of Islands – LeetCode