My Java solution with HashSet


  • 0
    C

    My approach here is trying to distinguish the shape of certain island by strings. I isolate each island in a small matrix and keep record of the distribution of 0 and 1. For an example,

    1 1 0 1 1
    1 0 0 0 0
    0 0 0 0 1
    1 1 0 1 1

    There are 4 island and we can isolate each of them as below:
    0_1507432623582_81cb6ffc-abf7-4413-9b07-03e7e7d85963-image.png

    And string representation is 11#10#, 11#, 11#, 01#11# (use # as the end of a line) and we can use these strings to distinguish different shapes.

    Below is my solution.

    class Solution {
        
        public int numDistinctIslands(int[][] grid) {
            int height = grid.length;
            int width = grid[0].length;
            Set<String> shapeCodes = new HashSet<>();
            int count = 0;
            for(int r = 0; r < height; r++) {
                for(int c = 0; c < width; c++) {
                    if(grid[r][c] == 1) {
                        // the range of square
                        int[] hRange = new int[] {r, r};  // the height range of small matrix
                        int[] wRange = new int[] {c, c};  // the width range of small matrix
                        fillWith(grid, r, c, height, width, hRange, wRange);
                        if(shapeCodes.add(serialize(grid, hRange, wRange))) {  // if find a new shape, count++
                            count++;
                        }
                    }
                }
            }
            return count;
        }
        
        private void fillWith(int[][] grid, int r, int c, int height, int width, int[] hRange, int[] wRange) {
            if(grid[r][c] == 1) {
                grid[r][c] = 2;  // mark as status "2" -- the current island
                
                // update the range, which shows the boundary of small matrix
                hRange[0] = Math.min(r, hRange[0]);
                hRange[1] = Math.max(r, hRange[1]);
                wRange[0] = Math.min(c, wRange[0]);
                wRange[1] = Math.max(c, wRange[1]);
                
                if(r > 0) fillWith(grid, r - 1, c, height, width, hRange, wRange);
                if(r < height - 1) fillWith(grid, r + 1, c, height, width, hRange, wRange);
                if(c > 0) fillWith(grid, r, c - 1, height, width, hRange, wRange);
                if(c < width - 1) fillWith(grid, r, c + 1, height, width, hRange, wRange);
            }
        }
        
        // To serialize the shape as a string
        private String serialize(int[][] grid, int[] hRange, int[] wRange) {
            StringBuilder sb = new StringBuilder();
            for(int r = hRange[0]; r <= hRange[1]; r++) {
                for(int c = wRange[0]; c <= wRange[1]; c++) {
                    if(grid[r][c] == 2) {
                        sb.append(2);
                        grid[r][c] = 3;  // mark as status "3" -- the island that already visited
                    } else {
                        sb.append(0);
                    }
                    
                }
                sb.append("#");  // use "#" to mark the end of line
            }
            return sb.toString();
        }
        
    }
    

Log in to reply
 

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