Concise Java DFS Solution


  • 0
    W
    class Solution {
        private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        public int numDistinctIslands(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            
            HashSet<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) {
                        continue;
                    }
                    
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, sb, i, j, 0 , 0);
                    set.add(sb.toString());
                }
            }
            
            return set.size();
        }
        
        private void dfs(int[][] grid, StringBuilder sb, int i, int j, int xDir, int yDir) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
               || grid[i][j] == 0) {
                return;
            }
            
            grid[i][j] = 0;
            for (int[] dir : dirs) {
                sb.append(xDir + "" + yDir);
                dfs(grid, sb, i + dir[0], j + dir[1], xDir + dir[0], yDir + dir[1]);
            }
        }
    }
    

Log in to reply
 

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