Medium

题目描述

给你一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："xi==yi" 或 "xi!=yi"。这里，xi 和 yi 是小写字母（不一定不同），表示单字母变量名。

如果可以将整数分配给变量名，以便满足所有给定的方程，则返回 true；否则返回 false。

示例 1：

输入：equations = ["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2：

输入：equations = ["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

提示：

  • 1 <= equations.length <= 500
  • equations[i].length == 4
  • equations[i][0] 是小写字母
  • equations[i][1] 是 '=' 或 '!'
  • equations[i][2] 是 '='
  • equations[i][3] 是小写字母

解题思路

这是一个典型的并查集（Union-Find）问题。我们需要判断给定的等式和不等式是否存在矛盾。

解题思路：

  1. 分析问题本质：如果两个变量相等（a==b），那么它们应该在同一个连通分量中；如果两个变量不相等（a!=b），那么它们不能在同一个连通分量中。

  2. 两阶段处理：

    • 第一阶段：处理所有等式（==），使用并查集将相等的变量合并到同一个集合中
    • 第二阶段：检查所有不等式（!=），验证不等的变量是否在不同的集合中

  3. 并查集操作：

    • 初始化：每个变量都是独立的集合
    • 合并：将等式两边的变量合并
    • 查找：检查两个变量是否在同一个集合中

  4. 冲突检测：如果某个不等式的两个变量在同一个集合中，说明存在矛盾，返回 false

算法步骤：

  1. 创建并查集，支持 26 个小写字母
  2. 遍历所有等式，将相等的变量进行合并
  3. 遍历所有不等式，检查是否存在冲突
  4. 如果所有检查都通过，返回 true

这种方法的优势是能够有效处理传递性关系，例如如果 a==b 且 b==c，那么自动可以推导出 a==c。

代码实现

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        vector<int> parent(26);
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        
        function<int(int)> find = [&](int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };
        
        auto unite = [&](int x, int y) {
            parent[find(x)] = find(y);
        };
        
        // 处理等式
        for (const string& eq : equations) {
            if (eq[1] == '=') {
                unite(eq[0] - 'a', eq[3] - 'a');
            }
        }
        
        // 检查不等式
        for (const string& eq : equations) {
            if (eq[1] == '!') {
                if (find(eq[0] - 'a') == find(eq[3] - 'a')) {
                    return false;
                }
            }
        }
        
        return true;
    }
};

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        parent = list(range(26))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            parent[find(x)] = find(y)
        
        # 处理等式
        for eq in equations:
            if eq[1] == '=':
                unite(ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a'))
        
        # 检查不等式
        for eq in equations:
            if eq[1] == '!':
                if find(ord(eq[0]) - ord('a')) == find(ord(eq[3]) - ord('a')):
                    return False
        
        return True

public class Solution {
    public bool EquationsPossible(string[] equations) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }
        
        int Find(int x) {
            if (parent[x] != x) {
                parent[x] = Find(parent[x]);
            }
            return parent[x];
        }
        
        void Unite(int x, int y) {
            parent[Find(x)] = Find(y);
        }
        
        // 处理等式
        foreach (string eq in equations) {
            if (eq[1] == '=') {
                Unite(eq[0] - 'a', eq[3] - 'a');
            }
        }
        
        // 检查不等式
        foreach (string eq in equations) {
            if (eq[1] == '!') {
                if (Find(eq[0] - 'a') == Find(eq[3] - 'a')) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

var equationsPossible = function(equations) {
    const parent = Array.from({length: 26}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function unite(x, y) {
        parent[find(x)] = find(y);
    }
    
    // 处理等式
    for (const eq of equations) {
        if (eq[1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n·α(26)) ≈ O(n)，其中 n 是方程的数量，α 是阿克曼函数的反函数，在实际应用中可视为常数
空间复杂度O(26) = O(1)，只需要存储 26 个字母的并查集结构