Share my neat accepted Java solution!


  • 0
    I
    public class Solution {
        void findIsland(char[][] grid, int x, int y, HashSet<Integer> used) {
            int tag = 0;
            int rows = grid.length;
            int columns = grid[0].length;
            // up
            if (x > 0 && grid[x - 1][y] == '1') {
                tag = (x - 1) * columns + y;
                if (!used.contains(tag)) {
                    used.add(tag);
                    findIsland(grid, x - 1, y, used);
                }
            }
            // right
            if ( y < (columns - 1) && grid[x][y + 1] == '1') {
                tag = x * columns + y + 1;
                if (!used.contains(tag)) {
                    used.add(tag);
                    findIsland(grid, x, y + 1, used);
                }
            }
            // down
            if (x < (rows - 1) && grid[x + 1][y] == '1') {
                tag = (x + 1) * columns + y;
                if (!used.contains(tag)) {
                    used.add(tag);
                    findIsland(grid, x + 1, y, used);
                }
            }
            // left
            if(y > 0 && grid[x][y - 1] == '1') {
                tag = x * columns + y - 1;
                if (!used.contains(tag)) {
                    used.add(tag);
                    findIsland(grid, x, y - 1, used);
                }
            }
        }
    
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int result = 0;
            int rows = grid.length;
            int columns = grid[0].length;
            HashSet<Integer> used = new HashSet<Integer>();
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < columns; ++j) {
                    if (grid[i][j] == '1') {
                        int tag = i * columns + j;
                        if (!used.contains(tag)) {
                            used.add(tag);
                            result ++;
                            findIsland(grid, i, j, used);
                        }
                    }
                }
            }
            return result;
        }
    }

Log in to reply
 

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