leetcode：990. 等式方程的可满足性

女爷i 2021-09-28 08:44 232阅读 0赞

*  **用户通过次数**70
 *  **用户尝试次数**111
 *  **通过次数**70
 *  **提交次数**296
 *  **题目难度**Medium

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

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

**示例 1：**

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

**示例 2：**

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

**示例 3：**

输入：["a==b","b==c","a==c"]
    输出：true

**示例 4：**

输入：["a==b","b!=c","c==a"]
    输出：false

**示例 5：**

输入：["c==c","b==d","x!=z"]
    输出：true

**提示：**

1.  `1 <= equations.length <= 500`
2.  `equations[i].length == 4`
3.  `equations[i][0]` 和 `equations[i][3]` 是小写字母
4.  `equations[i][1]` 要么是 `'='`，要么是 `'!'`
5.  `equations[i][2]` 是 `'='`
    
        package LeetCode;
        
        import java.util.ArrayList;
        import java.util.HashMap;
        import java.util.List;
        
        public class EquationsPossible {
            HashMap<Character, Character> map = new HashMap<>();
        
            public boolean equationsPossible(String[] equations) {
                for (int i = 0; i < equations.length; i++) {
                    char s1 = equations[i].charAt(0);
                    char s2 = equations[i].charAt(3);
                    if (!map.containsKey(s1)) {
                        map.put(s1, s1);
                    }
                    if (!map.containsKey(s2)) {
                        map.put(s2, s2);
                    }
                    //首先处理所有==的时候
                    if (equations[i].contains("==")) {
                        //合并两个到根节点
                        union(s1, s2);
                    }
                }
                //把所有的相等的处理好后，处理不等于号的数据
                for (int i = 0; i < equations.length; i++) {
                    if (equations[i].contains("!=")) {
                        char s1 = equations[i].charAt(0);
                        char s2 = equations[i].charAt(3);
                        if (find(s1) == find(s2)) {
                            return false;
                        }
                    }
        
                }
                return true;
            }
        
            public void union(char s1, char s2) {
                //找到两个最终的根后进行合并
                map.put(find(s1), find(s2));
            }
        
            public char find(char x) {
                if (map.get(x) != x) {
                    //dfs进行深度搜索搜到最终的根
                    return find(map.get(x));
                } else {
                    return x;
                }
            }
        }