Java dfs solution, O(mn)


  • 0
    M

    Time complexity: O(mn)

    public class Solution {
        public int numIslands(char[][] grid) {
            if(grid==null || grid.length==0) return 0;
            char mark = '2';
            for(int i=0; i<grid.length; i++){
                for(int j=0; j<grid[0].length; j++){
                    if(grid[i][j]=='1'){
                        dfs(i, j, grid, mark);
                        mark++;
                    }
                }
            }
            return mark-'2';
        }
        
        private void dfs(int i, int j, char[][] grid, char mark){
            if(i<0 || j<0 || i>=grid.length || j>=grid[0].length || grid[i][j]!='1') return;
            grid[i][j] = mark;
            dfs(i-1, j, grid, mark);
            dfs(i+1, j, grid, mark);
            dfs(i, j-1, grid, mark);
            dfs(i, j+1, grid, mark);
        }
    }
    

Log in to reply
 

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