# [Java/C++] Clean Code

• Java

``````class Solution {
private static int[][] delta = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

public int numDistinctIslands(int[][] grid) {
int m = grid.length, n = grid[0].length;
Set<List<List<Integer>>> islands = new HashSet<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
List<List<Integer>> island = new ArrayList<>();
if (dfs(i, j, i, j, grid, m, n, island))
}
}
return islands.size();
}

private boolean dfs(int i0, int j0, int i, int j, int[][] grid, int m, int n, List<List<Integer>> island) {
if (i < 0 || m <= i || j < 0 || n <= j || grid[i][j] <= 0) return false;
island.add(Arrays.asList(i - i0, j - j0));
grid[i][j] *= -1;
for (int d = 0; d < 4; d++) {
dfs(i0, j0, i + delta[d][0], j + delta[d][1], grid, m, n, island);
}
return true;
}
}
``````

C++

``````class Solution {
public:
int numDistinctIslands(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
set<vector<vector<int>>> islands;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
vector<vector<int>> island;
if (dfs(i, j, i, j, grid, m, n, island))
islands.insert(island);
}
}
return islands.size();
}

private:
int delta[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0};

bool dfs(int i0, int j0, int i, int j, vector<vector<int>>& grid, int m, int n, vector<vector<int>>& island) {
if (i < 0 || m <= i || j < 0 || n <= j || grid[i][j] <= 0) return false;
island.push_back({i - i0, j - j0});
grid[i][j] *= -1;
for (int d = 0; d < 4; d++) {
dfs(i0, j0, i + delta[d][0], j + delta[d][1], grid, m, n, island);
}
return true;
}
};
``````

• Your solution is nice! But I am wondering how set compares two list<Integer> lists in java? if list1 has same elements as list2, are they equal in Set? Since I transform list into string in this question, so I am curious whether we really can directly use set.contains(list) to check whether list1 is equal to list2 under the condition that list1 and list2 have same elemets?

• Nice! I was wandering how to express each island.

• @tiandiao123 `Set<T>` compares `T` by calling `T.equals(Object other)`, in this case `ArrayList`. ArrayList inherit the equals(Obect other){...} from `List`, which is defined so that lists with same item in same order are equal lists.

I also focus on C++, so I'm always wondering how to generate such concise and clean codes like yours.
Taking this problem as example, I got a similar idea, that is record each island and shift them so that make coordinates of first point to (0,0). But it took me almost 40 minutes to write a very verbose solution.
So how can I get improved? Thank you !

• @alexander Thanks!Got it!

• @alexander said in [Java/C++] Clean Code:

``````    island.add(new ArrayList<Integer>(Arrays.asList(i - i0, j - j0)));
``````

Why not just this?

``        island.add(Arrays.asList(i - i0, j - j0));``

• @StefanPochmann Thank you for pointing out! Yes it is not necessary, and I don't know why I did it that way :)

• @JadenPan said in [Java/C++] Clean Code:

Taking this problem as example, I got a similar idea, that is record each island and shift them so that make coordinates of first point to (0,0). But it took me almost 40 minutes to write a very verbose solution.

Thank you for saying that. Just take some practice. Usually if you meet same problem or similar problem again and again, each time you will have a slightly different and probably better & cleaner approach to solve it. Verbose is not a big deal, most important thing is you get something that works :)

• @alexander Thank you, I'll keep working hard

• @alexander said in [Java/C++] Clean Code:

Arrays.asList(i - i0, j - j0)

Excuse me, what does Arrays.asList(int, int) do? I only know Arrays.asList(int[]) to change an int array to list.

• @w1024020103 Can't you look up the documentation? Can't you try it out? Can't you take a guess? And I don't think you actually know Arrays.asList(int[]). That creates a list of length 1, the single element being the whole int-array. That's pretty useless and thus I highly doubt that that's what you thought it does.

• Hi, @alexander. Thank you for your amazing solution.
I was wondering why you should return a boolean in your dfs function? I use void return type, it also works. In your dfs function, after go to four directions, it will always return true to main function. So I think

``````if (dfs(i, j, i, j, grid, m, n, island))
``````

this condition is unnecessary too. We can call dfs directly and after that, add island into islands. Correct me if I was wrong! Thank you.

``````class Solution {
public int numDistinctIslands(int[][] grid) {
Set<List<List<Integer>>> islands = new HashSet<>();
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<List<Integer>> island = new ArrayList<>();
dfs(grid, i, j, i, j, island);
}
}
}
return islands.size();
}
public void dfs(int[][] grid, int i, int j, int i0, int j0, List<List<Integer>> island) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
return;
}
grid[i][j] = -1;
island.add(Arrays.asList(i - i0, j - j0));
int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] d: dir) {
dfs(grid, i + d[0], j + d[1], i0, j0, island);
}
}
}
``````

• oops! It's my fault. I didn't noticed that the entrance to go to dfs in your solution is different from me. In your solution, you will try every cells as entrance. But when you met a 0 or -1, you will return false. Only if you met 1, you will continue to search four directions and finally return true to let "islands" add "island".

``````for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
List<List<Integer>> island = new ArrayList<>();
if (dfs(i, j, i, j, grid, m, n, island))
}
}
``````

• Nice.
My solution beats 98%. I just use the direction string and hash it. :)

``````public int numDistinctIslands(int[][] grid) {
Set<String> set = new HashSet<>();
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
if(grid[i][j] != 0) {
StringBuilder sb = new StringBuilder();
dfs(grid, i, j, sb, "o"); // origin
grid[i][j] = 0;
}
}
}
return set.size();
}
private void dfs(int[][] grid, int i, int j, StringBuilder sb, String dir) {
if(i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] == 0) return;
sb.append(dir);
grid[i][j] = 0;
dfs(grid, i-1, j, sb, "u"); // up
dfs(grid, i+1, j, sb, "d"); // down
dfs(grid, i, j-1, sb, "l"); // left
dfs(grid, i, j+1, sb, "r"); // right
sb.append("b"); // back
}``````

• I'm wondering if DFS is favored over BFS when doing search in the matrix/graph?
The code looks shorter for DFS.

• What's the complexity of your code?

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