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

深藏阁楼爱情的钟 2023-02-16 04:26 150阅读 0赞

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

# 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 时间复杂度 ##

![在这里插入图片描述][20200608110956411.png]

## 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) { 
            
            // 第一趟遍历将相等的标注为1
            for(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 这种情况直接返回false
                    return 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，直接返回false
                        return false;
                    }
                    if(bfs(p, q)){ 
                        // bfs的查找和p相等的，看看能否找到q
                        // 如果能找到就说明p==q，无法满足p!=q，返回false
                        return 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) { 
            
            // 第一趟遍历将相等的标注为1
            for(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 这种情况直接返回false
                    return 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，直接返回false
                        return false;
                    }
                    if(notEqual[p][q] == 1){ 
                        continue;
                    }
                    if(bfs(p, q)){ 
                        // bfs的查找和p相等的，看看能否找到q
                        // 如果能找到就说明p==q，无法满足p!=q，返回false
                        return 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);
                        }
                    }
                }
            }
            // 这个时候已经访问过的行i元素，肯定与target不相等，记录下来避免重复判断
            for(int i = 0; i < 26; i++){ 
                if(visited[i] == 1){ 
                    notEqual[i][target] = 1;
                    notEqual[target][i] = 1;
                }
            }
            return false;
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200608120035109.png]

## 3.4 空间复杂度 ##

O(C\*C)

# 4 DFS #

## 4.1 思路 ##

既然有BFS，那么也可以DFS。

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

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

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

第二趟处理不等的：

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

## 4.2 代码 ##

class Solution { 
        private int[][] matrix = new int[26][26];
        // 0表示未访问过p和q，1代表已访问过且p和q相等，2表示本趟dfs正在访问p和q且关系未知
        private int[][] notEqual = new int[26][26];
        public boolean equationsPossible(String[] equations) { 
            // 第一趟遍历将相等的标注为1
            for(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 这种情况直接返回false
                    return false;
                }
            }
    
            // 第二趟处理不等的
            for(String str : equations){ 
                if(str.contains("!=")){ 
                    if(dfs(str.charAt(0)- 'a', str.charAt(3)- 'a')){ 
                        // dfs的查找和p相等的，看看能否找到q
                        // 如果能找到就说明p==q，无法满足p!=q，返回false
                        return false;
                    }
                }
            }
            return true;
        }
    
        private boolean dfs(int source, int target){ 
            if(notEqual[source][target] == 1){ 
                // 访问过且p和q不相等
                return false;
            }
            if(matrix[source][target] == 1){ 
                // 未访问过，但他们相等
                return true;
            }
            // 标记本趟dfs正在访问，此时p和q关系未知
            // 防止重复遍历
            notEqual[source][target] = 2;
            
            for(int i = 0; i < 26; i++){ 
                if(matrix[source][i] == 1 && notEqual[i][target] != 2 && dfs(i, target)){ 
                    // 和source相等的i元素，还没有判断过i和target关系，且通过dfs证明i和target相等
                    // 那么此时source和target就相等，返回true
                    return true;
                }
            }
            // 标记已访问过且p和q不相等
            notEqual[source][target] = 1;
            return false;
        }
    }

## 4.3 时间复杂度 ##

![在这里插入图片描述][20200608144152696.png]

## 4.4 空间复杂度 ##

O(C\*C)

[20200608110956411.png]: https://img-blog.csdnimg.cn/20200608110956411.png
[20200608120035109.png]: https://img-blog.csdnimg.cn/20200608120035109.png
[20200608144152696.png]: https://img-blog.csdnimg.cn/20200608144152696.png