Sunday, August 01, 2021

LeetCode, 200, Number of islands

To solve LeetCode question 200, there is already one good explanation of how to solve it.
The basic idea is to use tree traverse algorithm (dfs or bfs) to check the adjacent land.

Here is my Javascript solution:

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0;
    if (grid == null || grid.length === 0) {
        return 0;
    }

    let row = grid.length;
    let col = grid[0].length;
    function dfs(ij) {
        if (i > row - 1 || j > col -1 || i0 || j < 0) {
            return;
        }
        if (grid[i][j] === "1") {
            grid[i][j] = "0";
            dfs(i+1,j); //down
            dfs(i,j+1); //right
            dfs(i-1,j); //up
            dfs(i,j-1); //left
        }
    }

    for (let i=0i<rowi++) {
        for (let j=0j<colj++) {
            if (grid[i][j] === "1") {
                grid[i][j] = "0";
                dfs(i+1,j); //down
                dfs(i,j+1); //right
                dfs(i-1,j); //up
                dfs(i,j-1); //left
                count++;
            }
        }
    }

    return count;
};

var grid = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
];
console.log(result = numIslands(grid));
console.assert(result === 1);

grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
];
console.log(result = numIslands(grid));
console.assert(result === 3);
    
grid = [
    ["1","1","1"],
    ["0","1","0"],
    ["1","1","1"]
];
console.log(result = numIslands(grid));
console.assert(result === 1);



No comments: