694. Number of Distinct Islands

time: O(mn)

space: O(mn)

class Solution {
    public int numDistinctIslands(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Set<String> res = new HashSet<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    StringBuilder shape = new StringBuilder();
                    //System.out.println("i:"+i+"j:"+j);
                    dfs(grid, i, j, shape);
                    //System.out.println(shape.toString());
                    res.add(shape.toString());
                }
            }
        }
        return res.size();
    }
    
    int dirs[][] = {{0,-1}, {0,1}, {-1,0}, {1,0}};
    private void dfs(int[][] grid, int i, int j, StringBuilder shape) {
        for (int d = 0; d < dirs.length; d++) {
            int x = i + dirs[d][0];
            int y = j + dirs[d][1];
            
            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
                //System.out.println("d:"+d+",x:"+x+",y:"+y);
                grid[x][y] = 0;
                shape.append(d); // add dir number in shape
                dfs(grid, x, y, shape);
            }
        }
        shape.append("_"); // for real unique shape operation
    }
}

use normal gen String way

class Solution {
    int dirs[][] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public int numDistinctIslands(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Set<String> set = new HashSet<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    List<int[]> cells = new ArrayList<>();
                    getIslands(grid, i, j, cells);
                    
                    String island = getIslandsStr(cells);
                    set.add(island);
                }
            }
        }
        return set.size();
    }
    private void getIslands(int[][] grid, int i, int j, List<int[]> cells) {
        
        grid[i][j] = 0;
        cells.add(new int[]{i, j});
        
        for (int dir[] : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (! (inArea(grid, x, y) && grid[x][y] == 1 )) {
                continue;
            }
            getIslands(grid, x, y, cells);
        }
    }
    private boolean inArea(int[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
    private String getIslandsStr(List<int[]> cells) {
        StringBuilder sb = new StringBuilder();
        int x = cells.get(0)[0];
        int y = cells.get(0)[1];
        for (int[] cell : cells) {
            sb.append((cell[0]-x) + ":" + (cell[1]-y) + ":");
        }
        return sb.toString();
    }
} 

/*
dfs
T: O(mn)
S: O(mn)

1. 
Set<String> set;
if(grid[i][j] == 1) {
    generateIslandString(i, j);
    add to set
}

return set.size()

2. generateIslandString(i, j)
collect 1's cell all cordinates
these cordinates should substract the first cordinate

so for example 

  0 1 2 3 4

0  1 1 0 0 0
1  1 1 0 0 0
2  0 0 0 1 1
3  0 0 0 1 1  

2,3 2,4  
3,3 3,4    
=> these cordinates should substract the first cordinate
0,0  0,1
1,0  1,1

same as left up's island
0,0  0,1
1,0  1,1

save these new cordinates in a array[]

return String(array[]);

*/