Leetcode 694) Number of Distinct Islands

21 Oct 2021 in Algorithms

My Answer

class Solution {
    public int numDistinctIslands(int[][] grid){
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        Set<String> distinctIslands = new HashSet<>(); 
        for(int i=0;i<grid.length;i++){
            for(int j =0;j<grid[0].length;j++){
                if(!visited[i][j] && grid[i][j]==1){
                    String result=dfs(i,j,grid,visited);
                    distinctIslands.add(result);
                }
            }
        }
        int size = distinctIslands.size(); 
        return size;
    }

    public String dfs(int i , int j , int[][] grid, boolean[][] visited){
        visited[i][j]=true;
        int[][] position =  {{-1,0},{1,0},{0,-1},{0,1}}  ;
        String[] direction =  {"L","R","D","U"};

        String res = "";
        for(int k=0;k<position.length;k++){
            int x = i+position[k][0];
            int y = j+position[k][1];
            if(x>=0 && x<visited.length && y>=0 && y<visited[0].length){
                if(!visited[x][y] && grid[x][y]==1){
                    res+=direction[k];
                    res+=dfs(x,y,grid,visited);
                }
            }
        }
        res+="E";
        return res;
    }
}

Other Answer

class Solution {
    public int numDistinctIslands(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        //store island shape
        Set<String> islands = new HashSet<>();

        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == 1) {
                    StringBuilder current = new StringBuilder();
                    dfs(i, j, '0', grid, current);

                    islands.add(current.toString());
                }
            }
        }

        return islands.size();
    }

    public void dfs( int row, int col, char dir, int[][] grid, StringBuilder current){
        if(row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] == 0) {
            return;
        }

        grid[row][col] = 0;
        current.append(dir);
        dfs(row + 1, col, 'D', grid, current);
        dfs(row - 1, col, 'U', grid, current);
        dfs(row, col + 1, 'R', grid, current);
        dfs(row, col - 1, 'L', grid, current);
        current.append(dir);

    }
}