Clean Java bfs solution without using extra space (3 ms)


  • 1
    S
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                   count++;
                   bfs(grid, i, j);
                }
            }
        }
        return count;
    }
    
    private void bfs(char[][] grid, int i, int j) {
        if (grid[i][j] <= '0') return;
        grid[i][j] = '#';
        if (i > 0) bfs(grid, i - 1, j);
        if (i < grid.length - 1) bfs(grid, i + 1, j);
        if (j > 0) bfs(grid, i, j - 1);
        if (j < grid[0].length - 1) bfs(grid, i, j + 1);
    }

  • 0
    S

    your solution is dfs rather than bfs


  • 0
    S

    you are right, thank you for pointing it out


  • 0

    Just a reminder, bfs cannot be implemented by using recursion. You need use queue. dfs is the one which uses recursion to implement. But still thank you for the clean dfs solution with no extra space! :)


  • 0
    S

    @Nakanu It actually use extra space. When we use recursion, we use the system stack.


  • 0

    @scott.shao.5 Yea. That is true. Just talking about the difference.


Log in to reply
 

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