Clean java solution (DFS)


  • 0
    L

    Not much difference with other DFS method.
    To distinguish the shape of island, I use a string to encode visiting sequence.

    class Solution {
        int[][] dirs = {{-1,0},{0,-1},{1,0},{0,1}};
        String s = "";
        boolean[][] visited;
        public int numDistinctIslands(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            HashSet<String> hs = new HashSet<>();
            int m = grid.length;
            int n = grid[0].length;
            visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1 && !visited[i][j]) {
                        s = "";
                        dfs(grid, i, j, m, n, 0);
                        hs.add(s);
                    }
                }
            }
            return hs.size();
        }
    
        private void dfs(int[][] grid, int i, int j, int m, int n, int mark) {
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || visited[i][j]) return;
            visited[i][j] = true;
            s += mark;//mark direction
            for (int k = 0; k < 4; k++) {
                dfs(grid, i + dirs[k][0], j + dirs[k][1], m, n, k + 1);
            }
            s += "-";//mark finishing current position
        }
    }
    

  • 0
    M

    @lidaxia Could you help me understand the importance of the line

     s += "-"; //mark finishing current position 

    Why we have to mark the finishing current position?

    I thought recording DFS visiting direction for each island is good enough to determine the shape of the island. However without this line of code, some test cases' output will be off by 1.
    Thank you in advance.


Log in to reply
 

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