夯实算法-等式方程的可满足性

题目：LeetCode

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] 和 equations[i][3] 是小写字母
• equations[i][1] 要么是 '='，要么是 '!'
• equations[i][2] 是 '='

解题思路

创建一个26*26的数组，用来存取字母间的关系：

• 1.如果数组relation[i][j] = 1,那么说明i表示的字母和j表示的字母对应的数值相同
• 2.如果数组relation[i][j] = 0,那么说明i表示的字母和j表示的字母对应的数值不知道是否相同
• 3.如果数组relation[i][j] = -1,那么说明i表示的字母和j表示的字母对应的数值不相同 自己和自己肯定相同，然后把题目给的存一下，注意如果出现了矛盾就返回false，然后用三个for来判断是否出现a==b,b==c,但是a!=c这样的情况，出现了就直接返回false。 最后返回true

代码实现

public boolean equationsPossible(String[] equations) {
    int[][] relation = new int[26][26];
    for(int i = 0; i < 26; i++) relation[i][i] = 1;
    for(int i = 0; i < equations.length; i++){
        char flag = equations[i].charAt(1);
        int x = equations[i].charAt(0) - 'a';
        int y = equations[i].charAt(3) - 'a';
        if(flag == '!' && relation[x][y] != 1){
            relation[x][y] = -1;
            relation[y][x] = -1;
        }
        else if(flag == '=' && relation[x][y] != -1) {
            relation[x][y] = 1;
            relation[y][x] = 1;
        }
        else return false;
    }

    for(int i = 0; i < 26; i++){
        for(int j = 0; j < 26; j++){          
            for(int k = 0; k < 26; k++){
                if(relation[i][j] == 1 && relation[j][k] == 1){
                    if(relation[i][k] == -1) return false;
                    else {
                        relation[i][k] = 1;
                        relation[k][i] = 1;
                    }    
                }
            }
        }
    }
    return true;
}
复制代码

复杂度分析

• 时间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">O(N^2)</annotation></semantics></math>O(N2)
• 空间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">O(N^2)</annotation></semantics></math>O(N2)