算法-并查集/BFS-等式方程的可满足性

1 题目概述

1.1 题目出处

https://leetcode-cn.com/problems/satisfiability-of-equality-equations/

1.2 题目描述

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

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

示例 1：

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

输出：[“ba","ab”]
输入：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：

输入：[“ab","bc”,“a==c”]
输出：true
示例 4：

输入：[“ab",“b!=c”,"ca”]
输出：false
示例 5：

输入：[“cc","bd”,“x!=z”]
输出：true

2 并查集

2.1 思路

遍历两趟，第一趟遍历将相等的加入一个并查集。

第二趟处理不等的，如果同属一个并查集则判定为失败。

2.2 代码

class Solution {public boolean equationsPossible(String[] equations) {int[] records = new int[26];int[] unionFindSet = new int[26];for(int i = 0; i < 26; i++){unionFindSet[i] = i;}// 第一趟遍历将相等的加入一个并查集for(String str : equations){if(str.contains("==")){char p = str.charAt(0);char q = str.charAt(3);if(p == q){continue;}union(unionFindSet, p - 'a', q - 'a');}else if(str.charAt(0) == str.charAt(3)){return false;}}// 第二趟处理不等的for(String str : equations){if(str.contains("!=")){char p = str.charAt(0);char q = str.charAt(3);if(find(unionFindSet, p - 'a') == find(unionFindSet, q - 'a')){return false;}}}return true;}private void union(int[] unionFindSet, int p, int q){int left = find(unionFindSet, p);int right = find(unionFindSet, q);if(left == right){return;}unionFindSet[left] = unionFindSet[right];}private int find(int[] unionFindSet, int p){int son = p;while(unionFindSet[p] != p){p = unionFindSet[p];}while(unionFindSet[son] != son){int tmp = unionFindSet[son];unionFindSet[son] = p;son = tmp;}return p;}
}

2.3 时间复杂度

2.4 空间复杂度

O(C)

• C为字符集大小

3 BFS

3.1 思路

将两个元素之间的关系用矩阵表示：

• M[i, j] = 0表示i和j不相等
• M[i, j] = 1表示i和j相等

遍历两趟，第一趟遍历将相等的对应的矩阵格子设为1。

第二趟处理不等的：

• matrix[p][q] == 1时返回false
• 否则对第一个元素p进行bfs，只要找到跟p相等的元素x等于q，则说明p==q，不可能满足p!=q，返回false。

3.2 代码

• 初始版本

class Solution {private LinkedList<Integer> queue = new LinkedList<>();private int[][] matrix = new int[26][26];public boolean equationsPossible(String[] equations) {// 第一趟遍历将相等的标注为1for(String str : equations){if(str.contains("==")){char p = str.charAt(0);char q = str.charAt(3);matrix[p - 'a'][q - 'a'] = 1; matrix[q - 'a'][p - 'a'] = 1; }else if(str.charAt(0) == str.charAt(3)){// 顺便判断如果p!=p 这种情况直接返回falsereturn false;}}// 第二趟处理不等的for(String str : equations){if(str.contains("!=")){int p = str.charAt(0)- 'a';int q = str.charAt(3)- 'a';if(matrix[p][q] == 1){// 已经有p==q但又遇到p!=q，直接返回falsereturn false;}if(bfs(p, q)){// bfs的查找和p相等的，看看能否找到q// 如果能找到就说明p==q，无法满足p!=q，返回falsereturn false;}}}return true;}private boolean bfs(int source, int target){queue.add(source);int[] visited = new int[26];while(queue.size() > 0){int row = queue.poll();visited[row] = 1;for(int i = 0; i < 26; i++){if(matrix[row][i] == 1){if(i == target){return true;}if(visited[i] != 1){queue.add(i);}}}}return false;}
}

• 记录不相等数字

class Solution {private LinkedList<Integer> queue = new LinkedList<>();private int[][] matrix = new int[26][26];// 记录已经确定不相等的元素private int[][] notEqual = new int[26][26];public boolean equationsPossible(String[] equations) {// 第一趟遍历将相等的标注为1for(String str : equations){if(str.contains("==")){char p = str.charAt(0);char q = str.charAt(3);matrix[p - 'a'][q - 'a'] = 1; matrix[q - 'a'][p - 'a'] = 1; }else if(str.charAt(0) == str.charAt(3)){// 顺便判断如果p!=p 这种情况直接返回falsereturn false;}}// 第二趟处理不等的for(String str : equations){if(str.contains("!=")){int p = str.charAt(0)- 'a';int q = str.charAt(3)- 'a';if(matrix[p][q] == 1){// 已经有p==q但又遇到p!=q，直接返回falsereturn false;}if(notEqual[p][q] == 1){continue;}if(bfs(p, q)){// bfs的查找和p相等的，看看能否找到q// 如果能找到就说明p==q，无法满足p!=q，返回falsereturn false;}}}return true;}private boolean bfs(int source, int target){queue.add(source);int[] visited = new int[26];while(queue.size() > 0){int row = queue.poll();visited[row] = 1;for(int i = 0; i < 26; i++){if(matrix[row][i] == 1){if(i == target){return true;}if(visited[i] != 1){queue.add(i);}}}}for(int i = 0; i < 26; i++){if(visited[i] == 1){notEqual[i][target] = 1;notEqual[target][i] = 1;}}return false;}
}

3.3 时间复杂度

3.4 空间复杂度

O(C*C)