Share my python solution: Connected-component labeling algorithm

• The idea is based on Connected-component labeling. The disjoint-set (union find) implementation is based on this one.

``````from collections import defaultdict

# disjoint-set node
class DsNode:
def __init__(self):
self.rank = 0
self.parent = self

class DisjointSets:
# DisjointSets Constructors and public methods.
def __init__(self):
self._sets = defaultdict(DsNode)

def find(self, x):
# path compression
while x.parent is not x:
x.parent = x.parent.parent
x = x.parent
return x

def findByLabel(self, label):
return self.find(self._sets[label])

def unionByLabel(self, labelA, labelB):
# union by rank
a, b = self.find(self._sets[labelA]), self.find(self._sets[labelB])
if a is not b:
if a.rank > b.rank:
b.parent = a
else:
a.parent = b
if a.rank == b.rank:
b.rank += 1

# Connected-component labeling algorithm
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
rows = len(board)
if rows > 2:
cols = len(board[0])
if cols > 2:
ds = DisjointSets()
dummy = rows * cols
max_row_index, max_col_index = rows - 1, cols - 1
labels, next_label = [[0] * cols for _ in range(rows)], 1
# connect 'O's in 1st column to dummy node
for row in xrange(rows):
if board[row][0] == 'O':
labels[row][0] = dummy
# connect 'O's in 1st row to dummy node
for col in xrange(1, cols):
if board[0][col] == 'O':
labels[0][col] = dummy

for row in xrange(1, rows):
for col in xrange(1, cols):
if board[row][col] == 'O':
# check north and west cells
north, west = row - 1, col - 1
if board[north][col] == 'O':
# use the label of north cell
labels[row][col] = labels[north][col]
if board[row][west] == 'O':
if labels[row][col] == 0:
# current cell not labeled, use the label of west cell
labels[row][col] = labels[row][west]
elif labels[row][col] != labels[row][west]:
# union the two labels of north and west cells
ds.unionByLabel(labels[row][col], labels[row][west])
if labels[row][col] == 0:
# current cell not labeled: must be an isolated cell. Use next label
labels[row][col] = next_label
next_label += 1
if row == max_row_index or col == max_col_index:
# union boundary cells with dummy node
ds.unionByLabel(dummy, labels[row][col])

dummy = ds.findByLabel(dummy)
# scan board, check whether an 'O' cell is connected to dummy node
for row in xrange(1, max_row_index):
for col in xrange(1, max_col_index):
if board[row][col] == 'O' and ds.findByLabel(labels[row][col]) is not dummy:
# capture cell if it is not connected to dummy node
board[row][col] = 'X'
``````

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