LeetCode 990. Satisfiability of Equality Equations

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2019/02/12/LeetCode-990-Satisfiability-of-Equality-Equations/

访问原文「LeetCode 990. Satisfiability of Equality Equations」

题目要求

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

Input: [“a==b”,”b!=a”]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second. There is no way to assign the variables to satisfy both equations.

Example 2:

Input: [“b==a”,”a==b”]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

Input: [“a==b”,”b==c”,”a==c”]
Output: true

Example 4:

Input: [“a==b”,”b!=c”,”c==a”]
Output: false

Example 5:

Input: [“c==c”,”b==d”,”x!=z”]
Output: true

Note:

1. 1 <= equations.length <= 500
2. equations[i].length == 4
3. equations[i][0] and equations[i][3] are lowercase letters
4. equations[i][1] is either '=' or '!'
5. equations[i][2] is '='

题意解析

给出一个字符串数组，每个字符串的长度为4，中间两个字符为==或者!=，而第一个和最后一个为字母，代表一个数字。
判断这些等式是否都能满足。

解法分析

我的解法是这样的，找出中间两个字符为==的左右字符串，将每个字符相等的字符集合求出来。
然后对中间两个字符为!=的字符串判断，是否某个字符的相等字符集合中存在另外一个字符，存在则返回false。
如果都满足条件则返回true。

但是我的解法并不是最优的，主要是没有利用只有26个字符，以及深度优先的方式判断相等的字符集合。更好的方式可以看官方的解答，或者这个牛人的解答，点击前往

解题代码

public boolean equationsPossible(String[] equations) {
    if (null == equations || equations.length <= 0) {
        return true;
    }
    Map<Character, Set<Character>> values = new HashMap<>();
    for (String eq : equations) {
        char[] eqs = eq.toCharArray();
        if (eqs[1] == '=') {
            if (eqs[0] == eqs[3]) {
                continue;
            } else {
                if(!values.containsKey(eqs[0]) && !values.containsKey(eqs[3])){
                    values.put(eqs[0], new HashSet<>());
                    values.get(eqs[0]).add(eqs[3]);

                    values.put(eqs[3], new HashSet<>());
                    values.get(eqs[3]).add(eqs[0]);
                }else if(!values.containsKey(eqs[0])){
                    values.put(eqs[0], new HashSet<>());
                    values.get(eqs[0]).add(eqs[3]);
                    values.get(eqs[0]).addAll(values.get(eqs[3]));

                    for(char c : values.get(eqs[3])){
                        if(c != eqs[3]) {
                            values.get(c).add(eqs[0]);
                        }
                    }
                    values.get(eqs[3]).add(eqs[0]);
                }else if(!values.containsKey(eqs[3])){
                    values.put(eqs[3], new HashSet<>());
                    values.get(eqs[3]).add(eqs[0]);
                    values.get(eqs[3]).addAll(values.get(eqs[0]));

                    for(char c : values.get(eqs[0])){
                        if(c != eqs[0]) {
                            values.get(c).add(eqs[3]);
                        }
                    }
                    values.get(eqs[0]).add(eqs[3]);
                }else{
                    values.get(eqs[0]).add(eqs[3]);
                    for(char c : values.get(eqs[0])){
                        if(c != eqs[0]) {
                            values.get(c).add(eqs[3]);
                        }
                        values.get(c).add(eqs[3]);
                    }

                    values.get(eqs[3]).add(eqs[0]);
                    for(char c : values.get(eqs[3])){
                        if(c != eqs[0]) {
                            values.get(c).add(eqs[3]);
                        }
                        values.get(c).add(eqs[0]);
                    }
                }
            }
        }
    }

    for (String eq : equations) {
        char[] eqs = eq.toCharArray();
        if (eqs[1] == '!') {
            if (eqs[0] == eqs[3]) {
                return false;
            } else {
                if(values.containsKey(eqs[0]) && values.get(eqs[0]).contains(eqs[3])){
                    return false;
                }else if(values.containsKey(eqs[3]) && values.get(eqs[3]).contains(eqs[0])){
                    return false;
                }
            }
        }
    }
    return true;
}