二维网格图中探测环

难度: Medium

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

示例 1：

输入：grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：

示例 2：

输入：grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

输入：grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
输出：false

提示：

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。

Submission

运行时间: 163 ms

内存: 58.8 MB

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x: int, y: int):
        self.parent[y] = x
    
    def findAndUnite(self, x: int, y: int) -> bool:
        parentX, parentY = self.find(x), self.find(y)
        if parentX != parentY:
            self.unite(parentX, parentY)
            return True
        return False

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        uf = UnionFind(m * n)
        for i in range(m):
            for j in range(n):
                if i > 0 and grid[i][j] == grid[i - 1][j]:
                    if not uf.findAndUnite(i * n + j, (i - 1) * n + j):
                        return True
                if j > 0 and grid[i][j] == grid[i][j - 1]:
                    if not uf.findAndUnite(i * n + j, i * n + j - 1):
                        return True
        return False

Explain

这个题解使用了并查集(Union-Find)的数据结构来解决问题。并查集是一种用于处理一些不相交集合的合并及查询问题的数据结构。这里，我们将二维网格中的每个格子视为一个节点，节点的编号可以通过行号和列号转换得到，即 i * n + j（i为行号，j为列号，n为列数）。当两个相邻的格子具有相同的值时，我们将它们所在的集合进行合并。如果在尝试合并两个集合时发现它们已经在同一个集合中，说明存在一个环。这是因为我们只有在发现两个相同的字符时才进行合并操作，所以如果两个已经在同一个集合中的节点尝试合并，意味着这两个节点是通过同一种字符相连的，因此形成了环。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))  # 初始化每个节点的父节点为自身
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def unite(self, x: int, y: int):
        self.parent[y] = x  # 将y的父节点设置为x
    
    def findAndUnite(self, x: int, y: int) -> bool:
        parentX, parentY = self.find(x), self.find(y)
        if parentX != parentY:
            self.unite(parentX, parentY)
            return True
        return False

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        uf = UnionFind(m * n)  # 初始化并查集
        for i in range(m):
            for j in range(n):
                if i > 0 and grid[i][j] == grid[i - 1][j]:
                    if not uf.findAndUnite(i * n + j, (i - 1) * n + j):
                        return True  # 发现环
                if j > 0 and grid[i][j] == grid[i][j - 1]:
                    if not uf.findAndUnite(i * n + j, i * n + j - 1):
                        return True  # 发现环
        return False  # 未发现环

Explore

路径压缩是并查集优化技术中的一种，它可以显著减少在查找节点的根节点时所需的时间。具体来说，当我们在执行`find`函数寻找某个元素的根节点时，路径压缩技术会使得这个元素及其所有祖先节点直接或间接地指向根节点。这样，下一次再查找这些节点或它们的任何子节点时，可以更快地直接到达根节点。因此，路径压缩减少了树的高度，有效地减少了查询和合并操作的时间复杂度，从而提高了并查集的整体效率。

在并查集中，每个集合表示一组互相连接的节点。当尝试合并两个已处于同一集合中的节点时，意味着这两个节点可以通过集合内的其他节点间接连接。这种情况下，如果再通过一个直接的连接尝试将它们合并，实际上在这两个节点之间就形成了至少两条不同的路径连接它们，从而形成了一个环。因此，当并查集检测到两个已经在同一个集合中的节点尝试合并时，我们可以确信在这个集合中存在至少一个环。

在这个题解中，`unite`函数简单地将一个节点的父节点设置为另一个节点，并没有使用按秩合并优化。按秩合并是另一种优化技术，其中“秩”通常代表集合的大小或树的深度。在按秩合并中，我们通常将较小或较浅的树合并到较大或较深的树上，这样可以防止树的深度快速增加，从而保持操作的效率。没有使用按秩合并的潜在问题是，合并操作可能导致树的深度增加，尤其是在频繁合并时，可能会形成较深的树结构，从而增加后续操作的时间复杂度。