NumberOfIslandsUnionFind.java

private class DisjointSet {
    private Map<String, String> lookup = new HashMap<>();

    public void init(int row, int col) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                String key  = i + "," + j;
                // initially key value is the same, meaning the parent of the disjoint set is itself, i.e., isolated or not initialized
                this.lookup.put(key, key);
            }
        }
    }

    /**
     * @param key "row,col" is the key in the mastrix
     * @return String, "row,col" of the parent of this key
     */
    public String find(String key) throws Exception {
        if (key == null || key.length() == 0 || !this.lookup.containsKey(key)) {
            throw new Exception(String.format("Invalid input key %s", key));
        }

        while (!key.equals(this.lookup.get(key))) {
            key = this.lookup.get(key);
        }

        return key;
    }

    public void union(String key1, String key2) throws Exception {
        if (key1 == null || key1.length() == 0 || key2 == null || key2.length() == 0) {
            throw new Exception(String.format("key1 %s or key2 %s not valid", key1, key2));
        }

        String parent1 = this.find(key1);
        String parent2 = this.find(key2);

        if (!parent1.equals(parent2)) {
            this.lookup.put(parent1, parent2);
        }
    }

}

public int numIslandsDisjoinSet(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }

    int row = grid.length;
    int col = grid[0].length;
    // key: row,col, val: row,col
    DisjointSet ds = new DisjointSet();
    ds.init(row, col);
    Set<String> islands = new HashSet<>();

    try {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    String key = i + "," + j;
                    // union right grid
                    if (j + 1 < col && grid[i][j + 1] == '1') {
                        ds.union(key, i + "," + (j + 1));
                    }
                    // union the below grid
                    if (i + 1 < row && grid[i + 1][j] == '1') {
                        ds.union(key, (i + 1) + "," + j);
                    }
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    islands.add(ds.find(i + "," + j));
                }
            }
        }
    } catch (Exception e) {
        System.err.println(e);
    }
    return islands.size();
}