Clean Java Solution : HashSet + BFS


  • 0
    S

    Using HashSet to record the unique shape of island

    BFS Version

    class Solution {
        private static final int[] xdir = new int[] {0, 0, -1, 1};
        private static final int[] ydir = new int[] {-1, 1, 0, 0};
        public int numDistinctIslands(int[][] grid) {
            if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            int m = grid.length, n = grid[0].length;
            Set<String> tokenSet = new HashSet<>();
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == 1) {
                        searchToken(i, j, i, j, grid, new StringBuilder(), tokenSet);
                    }
                }
            }
            return tokenSet.size();
        }
        
        private void searchToken(int x, int y, int orgx, int orgy, int[][] grid, StringBuilder sb, Set<String> tokenSet) {
            Deque<int[]> queue = new LinkedList<>();
            queue.offer(new int[] {x, y});
            grid[x][y] = 2;
            while(!queue.isEmpty()) {
                int size = queue.size();
                while(size-- > 0) {
                    int[] loc = queue.poll();
                    sb.append((loc[0] - orgx) + "," + (loc[1] - orgy) + ";");
                    for(int i = 0; i < xdir.length; i++) {
                        int xnext = loc[0] + xdir[i];
                        int ynext = loc[1] + ydir[i];
                        if(xnext >= 0 && ynext >= 0 && xnext < grid.length && ynext < grid[0].length && grid[xnext][ynext] == 1) {
                            grid[xnext][ynext] = 2;
                            queue.offer(new int[] {xnext, ynext});
                        }
                    }
                }
            }
            tokenSet.add(sb.toString());
        }
    }
    
    

    DFS version

    class Solution {
        private static final int[] xdir = new int[] {0, 0, -1, 1};
        private static final int[] ydir = new int[] {-1, 1, 0, 0};
        public int numDistinctIslands(int[][] grid) {
            if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            int m = grid.length, n = grid[0].length;
            Set<String> tokenSet = new HashSet<>();
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == 1) {
                        StringBuilder sb = new StringBuilder();
                        searchToken(i, j, i, j, grid, sb);
                        tokenSet.add(sb.toString());
                    }
                }
            }
            return tokenSet.size();
        }
        
        private void searchToken(int x, int y, int orgx, int orgy, int[][] grid, StringBuilder sb) {
            sb.append(x - orgx).append(",").append(y - orgy).append(";");
            for(int i = 0; i < xdir.length; i++) {
                int xnext = x + xdir[i];
                int ynext = y + ydir[i];
                if(xnext >= 0 && ynext >= 0 && xnext < grid.length && ynext < grid[0].length && grid[xnext][ynext] == 1) {
                    grid[xnext][ynext] = 2;
                    searchToken(xnext, ynext, orgx, orgy, grid, sb);
                }
            }
        }

Log in to reply
 

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