LeetCode 990. 等式方程的可满足性

Categories:

题目描述
思路分析
1. 解法一：并查集（推荐）
相似题目

题目描述

✅ 990. 等式方程的可满足性

思路分析

解法一：并查集（推荐）

核心思路：

先把所有等式 a==b 合并到同一集合。

再检查所有不等式 a!=b，若同属一集合则矛盾。

字母范围 26 个，规模固定。

复杂度分析：

时间复杂度：O(n * α(26))，其中 n 表示等式数量。

空间复杂度：O(1)。

class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                int a = eq.charAt(0) - 'a';
                int b = eq.charAt(3) - 'a';
                union(parent, a, b);
            }
        }

        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int a = eq.charAt(0) - 'a';
                int b = eq.charAt(3) - 'a';
                if (find(parent, a) == find(parent, b)) {
                    return false;
                }
            }
        }

        return true;
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    private void union(int[] parent, int a, int b) {
        int pa = find(parent, a);
        int pb = find(parent, b);
        if (pa != pb) {
            parent[pa] = pb;
        }
    }
}

func equationsPossible(equations []string) bool {
	parent := make([]int, 26)
	for i := 0; i < 26; i++ {
		parent[i] = i
	}

	find := func(x int) int {
		for parent[x] != x {
			parent[x] = parent[parent[x]]
			x = parent[x]
		}
		return x
	}

	union := func(a int, b int) {
		pa := find(a)
		pb := find(b)
		if pa != pb {
			parent[pa] = pb
		}
	}

	for _, eq := range equations {
		if eq[1] == '=' {
			a := int(eq[0] - 'a')
			b := int(eq[3] - 'a')
			union(a, b)
		}
	}

	for _, eq := range equations {
		if eq[1] == '!' {
			a := int(eq[0] - 'a')
			b := int(eq[3] - 'a')
			if find(a) == find(b) {
				return false
			}
		}
	}

	return true
}

相似题目

题目	难度	考察点
547. 省份数量	中等	并查集
721. 账户合并	中等	并查集
684. 冗余连接	中等	并查集
399. 除法求值	中等	并查集
1202. 交换字符串中的元素	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/71512261