694. Number of Distinct Islands

二刷 05/2022

Version #2 BFS

Hash each island into List<List<Integer>>

Each position is normalize by calculating the offset from the left top grid of the island

caveat: 这里如果用int[]是不work的，可能int array的hash function是由地址代替的

Runtime: 21 ms, faster than 30.36% of Java online submissions for Number of Distinct Islands.

Memory Usage: 54.5 MB, less than 20.22% of Java online submissions for Number of Distinct Islands.

class Solution {

    public int numDistinctIslands(int[][] grid) {

        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        // Find all points of an island and store them in List<int[]>

        // Since we iterate from smaller to larger indexes, the fisrt grid in the list is always the top left grid

        // Normalize an island by calculate the relative position of every point with the top left point

        // Store the island grid list in a hash set

        Set<List<List<Integer>>> islands = new HashSet<>();

        int rows = grid.length, cols = grid[0].length;

        boolean[][] visited = new boolean[rows][cols];

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (!visited[y][x] && grid[y][x] == 1) {

                    // Expand an island from starting point (x, y) and returns all of its grids

                    List<List<Integer>> island = findIsland(grid, y, x, visited);

                    islands.add(island);

                }

            }

        }

        return islands.size();

    }

    

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    List<List<Integer>> findIsland(int[][] grid, int y, int x, boolean[][] visited) {

        List<List<Integer>> island = new ArrayList<>();

        Queue<List<Integer>> que = new ArrayDeque<>();

        que.offer(Arrays.asList(y, x));

        visited[y][x] = true;

        while (!que.isEmpty()) {

            List<Integer> curr = que.poll();

            island.add(Arrays.asList(curr.get(0) - y, curr.get(1) - x));

            // iterate all 4 directions

            for (int i = 0; i < 4; i++) {

                int ny = curr.get(0) + dy[i];

                int nx = curr.get(1) + dx[i];

                // out of the boundary

                if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length) {

                    continue;

                }

                if (!visited[ny][nx] && grid[ny][nx] == 1) {

                    visited[ny][nx] = true;

                    que.offer(Arrays.asList(ny, nx));

                }

            }

        }

        return island;

    }

}

Test Cases:
[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
[[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]

一刷
Version #1 DFS
Hash each island by grids offset from its left most & top grid

58.50 %
class Solution {
    public int numDistinctIslands(int[][] grid) {
// when we see the left,top grid of an island, try to expand it
// keep track of each grid by its relative position, seperated by " "
// use a string to encode the shape of each island
Set<String> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == 1) {
dfs(grid, y, x, 0, 0, sb);
set.add(sb.toString());
sb.setLength(0);
}
}
}
return set.size();
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void dfs(int[][] grid, int y, int x, int offY, int offX, StringBuilder sb) {
sb.append(offY).append(" ").append(offX).append(" ");
grid[y][x] = 0;
for (int i = 0; i < 4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
if (nextX >= 0 && nextX < grid[0].length && nextY >= 0 && nextY < grid.length
&& grid[nextY][nextX] == 1) {
dfs(grid, nextY, nextX, offY + dy[i], offX  + dx[i], sb);
}
}
}
}