LeetCode : 694. Number of Distinct Islands

[congr]

https://leetcode.com/problems/number-of-distinct-islands/

[congr]

Almost the same question as "Number of Island", except for "distinct" shape

0011
0010

and

0110
0100  

are the same island shape, so don't count;

[congr]

class Solution {
    public int numDistinctIslands(int[][] grid) {
        Set<String> set = new HashSet();
        int num = 0;

        for (int i = 0; i<grid.length; i++) {
            for (int j = 0; j<grid[0].length; j++) {
                StringBuilder sb = new StringBuilder();
                if (grid[i][j] == 1 && dfs(grid, i, j, 0, 0, sb) > 0){
                    String s = sb.toString();
                    if (!set.contains(s)) {
                        set.add(s);
                        num++;
                    }
                }
            }
        }

        return num;
    }

    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    int dfs (int [][] grid, int y, int x, int di, int dj, StringBuilder sb) {
        if (grid[y][x] != 1) return 0;
        grid[y][x] = 3; // !!! visited

        sb.append(di+""+dj); // !!! y x index of island

        int cnt = 1; // !!! count this cell
        for (int k=0; k<4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (ny < grid.length && ny >= 0 && nx <grid[0].length && nx >=0) // inside
                cnt += dfs(grid, ny, nx, di+dy[k], dj+dx[k], sb);
        }

        return cnt;
    }
}