711. Number of Distinct Islands II

time: O(mn)

space: O(mn)

class Solution {
    private int dirs[][] = {{0,-1},{0, 1},{1, 0},{-1,0}};
    private int trans[][] = {{1,1},{1, -1},{-1, 1},{-1,-1}}; // 4 種不同的形狀, 之後在 xy 對調, 做對稱

    public int numDistinctIslands2(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Set<String> result = 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<>();
                    dfs(grid, i, j, cells);
                    String shape = normalize(cells); // key is how to disguise different shape
                    result.add(shape);
                }
            }
        }
        return result.size();
    }
    
    private void dfs(int[][] grid, int i, int j, List<int[]> cells) {
        
        cells.add(new int[]{i, j});
        grid[i][j] = 0;
        for (int dir[] : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1)) {
                continue;
            }
            dfs(grid, x, y, cells);
        }
    }
    
    private String normalize(List<int[]> cells) {
        List<String> forms = new ArrayList<>();
        // do 4 transition & reflection(2) , 4*2 = 8
        for (int tran[] : trans) {
            List<int[]> tranCells1 = new ArrayList<>();
            List<int[]> tranCells2 = new ArrayList<>();
            for (int cell[] : cells) {
                tranCells1.add(new int[]{cell[0]*tran[0], cell[1]*tran[1]}); // reflection 1
                tranCells2.add(new int[]{cell[1]*tran[1], cell[0]*tran[0]}); // reflection 2, cell, and tran
            }
            forms.add(getSortStr(tranCells1));
            forms.add(getSortStr(tranCells2));
        }
        
        Collections.sort(forms); // do entire sort again
        // at last, return entire String, I think is more easy to understand
        StringBuilder sb = new StringBuilder();
        for (String form : forms) {
            sb.append(form);
        }
        return sb.toString();
        // return forms.get(0); // at last, just use first String is ok
    }
    
    /*
        1. sort by cell x then y
        2. append all cells[] to String, but need minus first x, y (都去掉位移, 都剪掉起始點的平移)
    */
    private String getSortStr(List<int[]> cells) {
        // 1.
        Collections.sort(cells, (int a[], int b[]) -> {
            return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
        });
        int x = cells.get(0)[0]; // 2.
        int y = cells.get(0)[1];
        StringBuilder sb = new StringBuilder();
        for (int cell[] : cells) {
            sb.append( (cell[0] - x) + ":" + (cell[1] - y) + ":");
        }
        return sb.toString();
    }
}