Leet Code "200. Number of Islands" commentary

Overview

It seems that many foreign-affiliated companies conduct coding tests in interviews with engineers. The site of the past question of the coding test is Let Code I don't plan to take it, but I solve one question every day for studying

problem

200. Number of Islands Difficulty is Medium

You will be given the following input In a map-like image, 1 represents land and 0 represents the sea. An island is created on adjacent land The output required is the number of islands In the example below, there are 3 islands in the upper left, middle and lower right, so 3 is the output

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

solution

Look from the edge and repeat the following

1. If you find an island, mark all the land on that island as visited
2. Add 1 island counter

python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        
        #Make all the land on the island visited
        def check(i,j):            
            if grid[i][j]=="1":        
                #Make it visited
                grid[i][j]="2"                
                #Recursively visit adjacent lands on the top, bottom, left, and right
                if i-1>=0:
                    check(i-1,j)
                if j-1>=0:
                    check(i,j-1)
                if i+1<=len(grid)-1:
                    check(i+1,j)
                if j+1<=len(grid[0])-1:
                    check(i,j+1)                                            
        
        #Island counter
        count=0
            
        #grid[0][0]I will look at it in order from
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #If it was land
                if grid[i][j]=="1":
                    #Make all the land on the island visited
                    check(i,j)
                    #Add 1 island counter
                    count+=1                
        return count