711.Number of Distinct Islands II

Really Hard Question

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

1-Norm and Get Key is Important!!

class Solution {
    int[][] trans = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    public int numDistinctIslands2(int[][] grid) {
        Set<String> set = new HashSet<>();
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] != 0){
                    List<int[] > shape = new ArrayList<>();
                    dfs(grid, i, j, i, j, shape);
                    grid[i][j] = 0;
                    if(!shape.isEmpty()){
                        set.add(norm(shape));
                    }
                }
            }
        }
        return set.size();
    }
    public String norm(List<int[]> shape){
        List<String> forms = new ArrayList<>();
        for(int[] ts : trans){
            List<int[]> list1 = new ArrayList<>();
            List<int[]> list2 = new ArrayList<>();
            for(int[] cell : shape){
                list1.add(new int[]{cell[0] * ts[0], cell[1] * ts[1]});
                list2.add(new int[]{cell[1] * ts[0], cell[0] * ts[1]});
            }
            forms.add(getKey(list1));
            forms.add(getKey(list2));
        }
        Collections.sort(forms);
        return forms.get(0);
    }
    public String getKey(List<int[]> cells){
        Collections.sort(cells, new Comparator<int[]>(){
           @Override
            public int compare(int[] a, int[] b){
                if(a[0] != b[0]){
                    return a[0] - b[0];
                }
                else{
                    return a[1] - b[1];
                }
            }
        });
        StringBuilder sb = new StringBuilder();
        int baseX = cells.get(0)[0];
        int baseY = cells.get(0)[1];
        for(int[] cell : cells){
            sb.append("<"+ (cell[0] - baseX) +","+ (cell[1] - baseY) +">");
        }
        return sb.toString();
    }
    public void dfs(int[][] grid, int i, int j, int baseI, int baseJ, List<int[]> shape) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return;
        shape.add(new int[]{i - baseI, j - baseJ});
        grid[i][j] = 0;
        dfs(grid, i + 1, j, baseI, baseJ, shape);
        dfs(grid, i - 1, j, baseI, baseJ, shape);
        dfs(grid, i, j - 1, baseI, baseJ, shape);
        dfs(grid, i, j + 1, baseI, baseJ, shape);
    }
}