694. Number of Distinct Islands
和 200. Number of Islands 解法差不多。多出的部分是用一个 set 记录走的路径。
注意：DO NOT FORGET to add path for backtracking, otherwise, we may have same result when we count two distinct islands in some cases. 参考这个帖子。
Time = O(mn), Space = O(mn)
class Solution {
public int numDistinctIslands(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
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) {
StringBuilder sb = new StringBuilder();
dfsHelper("X", i, j, grid, sb);
set.add(sb.toString());
}
}
}
return set.size();
}
private void dfsHelper(String path, int i, int j, int[][] grid, StringBuilder sb) {
if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1 || grid[i][j] == 0) {
return;
}
sb.append(path);
grid[i][j] = 0;
dfsHelper("U", i - 1, j, grid, sb);
dfsHelper("D", i + 1, j, grid, sb);
dfsHelper("L", i, j - 1, grid, sb);
dfsHelper("R", i, j + 1, grid, sb);
sb.append("B");
}
}