Java solution - DFS


  • 0
    public class Solution {
        public int numIslands(char[][] grid) {
            if(grid.length == 0) {
                return 0;
            }
            
            int[][] ids = new int[grid.length][grid[0].length];//island ids
            int nextId = 0;
            for(int i = 0; i < grid.length; i++) {
                for(int j = 0; j < grid[0].length; j++) {
                    if(ids[i][j] == 0 && grid[i][j] == '1') {
                        ++nextId;
                        dfs(grid, i, j, ids, nextId);
                    }
                }
            }
            
            return nextId;
        }
        
        private void dfs(char[][] grid, int r, int c, int[][] ids, int nextId) {
            if(r < 0 || r == grid.length || c < 0 || c == grid[0].length) {
                return;
            }
            
            if(grid[r][c] == '0') {
                return;
            }
            
            if(ids[r][c] != 0) {
                return;
            }
            
            ids[r][c] = nextId;
            
            //traverse left
            dfs(grid, r, c - 1, ids, nextId);
            //traverse right
            dfs(grid, r, c + 1, ids, nextId);
            //traverse up
            dfs(grid, r - 1, c, ids, nextId);
            //traverse down
            dfs(grid, r + 1, c, ids, nextId);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.