accepted java solution!


  • 0
    T
    class Solution {
        Set<String> set = new HashSet<>();  
        public int numDistinctIslands(int[][] grid) {
             if(grid==null || grid.length<1){
                 return 0;
             }
             int count = 0;
             for(int i=0;i<grid.length;i++){
                 for(int j=0;j<grid[0].length;j++){
                     if(grid[i][j]==1){
                         List<Integer> temp = new ArrayList<>();
                         dfs(grid,i,j,temp);
                         if(check(temp)){
                             count++;
                         }
                     }
                 }
             }
             return count;
        }
        
        public boolean check(List<Integer> list){
            Collections.sort(list);
            int offset  = list.get(0);
            for(int i=0;i<list.size();i++){
                list.set(i,list.get(i)-offset);
            }
            
            StringBuilder sb = new StringBuilder();
            for(int ele:list){
                sb.append(ele+" ");
            }
            String str = sb.toString();
            if(set.contains(str)){
                return false;
            }
            set.add(str);
            return true;
        }
        
        public void dfs(int[][] grid,int row,int col,List<Integer> list){
               if(row<0||row>=grid.length||col<0||col>=grid[0].length||grid[row][col]==0){
                   return;
               }
               grid[row][col] = 0;
               list.add(row*grid[0].length+col);
               int[][] dirs = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
               for(int[] dir:dirs){
                   int x = dir[0]+row;
                   int y = dir[1]+col;
                   dfs(grid,x,y,list);
               }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.