694. Number of Distinct Islands

/**
 * DFS Recursive. This solution create a path signature of each island and save
 * it in a HashSet. HashSet keeps one copy of each distinct signature.
 *
 * Time Complexity: O(M * N) - All cells in the grids ar visited twice.
 *
 * Space Complexity: O(M * N) - This is for recursion stack and visited boolean
 * array
 *
 * M = Number of rows in the grid. N = Number of columns in the grid.
 */
class Solution {
    public int numDistinctIslands(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        if (grid.length == 1 && grid[0].length == 1) {
            if (grid[0][0] == 1) {
                return 1;
            } else {
                return 0;
            }
        }

        boolean[][] visited = new boolean[grid.length][grid[0].length];
        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] == 1 && !visited[i][j]) {
                    StringBuilder path = new StringBuilder();
                    dfsHelper(grid, i, j, visited, path, "o");
                    set.add(path.toString());
                }
            }
        }

        return set.size();
    }

    private void dfsHelper(int[][] grid, int i, int j, boolean[][] visited, StringBuilder path, String dir) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1 || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        path.append(dir);
        dfsHelper(grid, i + 1, j, visited, path, "d");
        dfsHelper(grid, i - 1, j, visited, path, "u");
        dfsHelper(grid, i, j + 1, visited, path, "r");
        dfsHelper(grid, i, j - 1, visited, path, "l");
        path.append("b");
    }
}