題目出處
難度
medium
題目分類
Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix
2026-07-24 一刷
個人範例程式碼 - 一刷 (2026/07/24)
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
ans = 0
h, w = len(grid), len(grid[0])
def dfs(i, j):
if i < 0 or i >= h or j < 0 or j >= w or grid[i][j] == "0":
return
grid[i][j] = "0"
dfs(i-1, j)
dfs(i, j-1)
dfs(i+1, j)
dfs(i, j+1)
return
for i in range(h):
for j in range(w):
if grid[i][j] == "1":
ans += 1
dfs(i, j)
return ans
算法說明
基礎的 DFS 題目，跟前幾天做的 【Leetcode】python - [695] Max Area of Island 個人解法筆記 在 DFS 方面的解題思路基本相同。
補充：下次解需要留意一個小細節 return, 或是 return None 都是有些多餘的干擾閱讀寫法，不如直接省略。
還有一個小細節需要注意：“0”, “1” 是 string 不是 int，別看太快。
Time Complexity
O(m*n) (整個 grid 掃過)
Space Complexity
O(m*n) (最壞情況，像是一條蛇，stack 需要把整個 grid 掃過，全部存進 stack)
Boundary conditions
- 注意邊界條件：i < 0 or i >= h or j < 0 or j >= w 這些出界都不合法
- 注意 [], [[]] 題目沒特別講, 但謹慎起見還是一開始就防呆處理