Problem
An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.
Given the grid grid represented as a string array, return the number of regions.
Note that backslash characters are escaped, so a '\' is represented as '\\'.
Example 1:
Input: grid = [" /","/ "]
Output: 2
Example 2:
Input: grid = [" /"," "]
Output: 1
Example 3:
Input: grid = ["/\\","\\/"]
Output: 5
Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.
Constraints:
n == grid.length == grid[i].length1 <= n <= 30grid[i][j]is either'/','\', or' '.
Solution (Java)
class Solution {
private int regions;
private int[] parent;
public int regionsBySlashes(String[] grid) {
int n = grid.length;
regions = n * n * 4;
unionFind(regions);
for (int row = 0; row < grid.length; ++row) {
int col = 0;
String str = grid[row];
char[] ch = str.toCharArray();
for (char c : ch) {
int index = row * n * 4 + col * 4;
if (c == '/') {
union(index, index + 3);
union(index + 1, index + 2);
} else if (c == ' ') {
union(index, index + 1);
union(index + 1, index + 2);
union(index + 2, index + 3);
} else {
union(index, index + 1);
union(index + 2, index + 3);
// ++i;
}
if (row != n - 1) {
union(index + 2, index + 4 * n);
}
if (col != n - 1) {
union(index + 1, index + 7);
}
++col;
}
}
return regions;
}
private void unionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
private void union(int p, int q) {
if (connected(p, q)) {
return;
}
--regions;
int i = root(p);
int j = root(q);
if (i > j) {
parent[i] = j;
} else {
parent[j] = i;
}
}
private boolean connected(int p, int q) {
return root(p) == root(q);
}
private int root(int index) {
while (index != parent[index]) {
parent[index] = parent[parent[index]];
index = parent[index];
}
return index;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).