My java solution using Union Find


  • 1
    L
    public void solve(char[][] board) {
        if(board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        UnionFind uf = new UnionFind(m,n);
        int cache = -1;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'O'){
                    if(i == 0 || i == m-1 || j == 0 || j == n-1){//judge four edges of board
                        if(cache == -1) cache = i*n + j;
                        else uf.union(cache,i*n + j);// union 'O' in four edges of board
                    }
                    if(j+1 < n && board[i][j+1] == 'O') uf.union(i*n+j,i*n+j+1);// union right direction
                    if(i+1 < m && board[i+1][j] == 'O') uf.union(i*n+j,(i+1)*n+j);// union down direction
                }
            }
        }
        if(cache == -1){// it shows four edges of board are all 'X'
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(board[i][j] == 'O') board[i][j] = 'X';// we just need set 'O' to 'X'
                }
            }
            return;
        }
        for(int i = 0; i < m; i++){// set 'O' to 'X' which 'O' is not connected with 'O' of cache
            for(int j = 0; j < n; j++){
                if(board[i][j] == 'O' && !uf.isConnected(cache,i*n+j))  board[i][j] = 'X';
            }
        }
        return;
    }
    private class UnionFind{
        int[] id;
        int[] rank;
        public UnionFind(int m,int n){
            id = new int[m*n];
            rank = new int[m*n];
            for(int i = 0; i < m*n; i++){
                id[i] = i;
                rank[i] = 1;
            }
        }
        public int find(int p){
            if(p != id[p]) id[p] = find(id[p]);
            return id[p];
        }
        public boolean isConnected(int p,int q){
            int pp = find(p);
            int qq = find(q);
            return pp == qq;
        }
        public void union(int p ,int q){
            int pp = find(p);
            int qq = find(q);
            if(pp == qq) return;
            if(rank[pp] > rank[qq]){
                id[qq] = pp;
                rank[pp] += rank[qq];
            }
            else{
                id[pp] = qq;
                rank[qq] += pp;
            }
        }
    }

Log in to reply
 

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