# My Java solution with HashSet

• My approach here is trying to distinguish the shape of certain island by strings. I isolate each island in a small matrix and keep record of the distribution of `0` and `1`. For an example,

1 1 0 1 1
1 0 0 0 0
0 0 0 0 1
1 1 0 1 1

There are 4 island and we can isolate each of them as below:

And string representation is `11#10#`, `11#`, `11#`, `01#11#` (use `#` as the end of a line) and we can use these strings to distinguish different shapes.

Below is my solution.

``````class Solution {

public int numDistinctIslands(int[][] grid) {
int height = grid.length;
int width = grid[0].length;
Set<String> shapeCodes = new HashSet<>();
int count = 0;
for(int r = 0; r < height; r++) {
for(int c = 0; c < width; c++) {
if(grid[r][c] == 1) {
// the range of square
int[] hRange = new int[] {r, r};  // the height range of small matrix
int[] wRange = new int[] {c, c};  // the width range of small matrix
fillWith(grid, r, c, height, width, hRange, wRange);
if(shapeCodes.add(serialize(grid, hRange, wRange))) {  // if find a new shape, count++
count++;
}
}
}
}
return count;
}

private void fillWith(int[][] grid, int r, int c, int height, int width, int[] hRange, int[] wRange) {
if(grid[r][c] == 1) {
grid[r][c] = 2;  // mark as status "2" -- the current island

// update the range, which shows the boundary of small matrix
hRange[0] = Math.min(r, hRange[0]);
hRange[1] = Math.max(r, hRange[1]);
wRange[0] = Math.min(c, wRange[0]);
wRange[1] = Math.max(c, wRange[1]);

if(r > 0) fillWith(grid, r - 1, c, height, width, hRange, wRange);
if(r < height - 1) fillWith(grid, r + 1, c, height, width, hRange, wRange);
if(c > 0) fillWith(grid, r, c - 1, height, width, hRange, wRange);
if(c < width - 1) fillWith(grid, r, c + 1, height, width, hRange, wRange);
}
}

// To serialize the shape as a string
private String serialize(int[][] grid, int[] hRange, int[] wRange) {
StringBuilder sb = new StringBuilder();
for(int r = hRange[0]; r <= hRange[1]; r++) {
for(int c = wRange[0]; c <= wRange[1]; c++) {
if(grid[r][c] == 2) {
sb.append(2);
grid[r][c] = 3;  // mark as status "3" -- the island that already visited
} else {
sb.append(0);
}

}
sb.append("#");  // use "#" to mark the end of line
}
return sb.toString();
}

}
``````

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