[LeetCode] 990. Satisfiability of Equality Equations

990. Satisfiability of Equality Equations

Medium

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

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

 

Example 1:

Input: equations = ["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: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

 

Constraints:

• 1 <= equations.length <= 500
• equations[i].length == 4
• equations[i][0] is a lowercase letter.
• equations[i][1] is either '=' or '!'.
• equations[i][2] is '='.
• equations[i][3] is a lowercase letter.

---

문제 풀이

1. a==b 와 같은 식이 주어진다.
2. 변수 사이에 들어가는 조건식은 != 혹은 == 이다. 
3. 즉 주어지는 모든 식들의 조건이 맞아야한다. 
4. 예를 들어 a==b, a!=b 가 주어진다면, 답은 False 이다. 
5. 반대로 a==b, b==a 이면 답은 True 이다. 
6. 여기서 a==b, b==c, a!=c 는 성립되지 않는다, 왜냐하면 a==b==c 인 상황에서 a==c 이기 때문이다.
7. 이를 고려할때, 그룹을 지어줘야하는 Union-Find 알고리즘을 사용할 수 있어 보인다. 
8. DFS, BFS 혹은 재귀함수로 풀수도 있겠지만, 소스코드가 더 복잡해질 수 있다.
9. a==b, b==c, a!=c 조건을 보면, a==b==c 인 상태는 결국 a, b, c 는 모두 같은 그룹에 있다고 생각할 수 있다.

소스 코드

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        hashTable = defaultdict()
        candidates = []
        def find(a, hashTable):
            if a == hashTable[a]:
                return a
            hashTable[a] = find(hashTable[a], hashTable)
            return hashTable[a]
        
        def union(a, b, hashTable):
            a_p = find(a, hashTable)
            b_p = find(b, hashTable)
            
            if a_p != b_p:
                hashTable[a_p] = b_p
        
        for i in range(ord('a'), ord('z') + 1):
            hashTable[chr(i)] = chr(i)
        
        for s in equations:
            a1 = s[0]
            a2 = s[3]
            if s[1] == '=':
                union(a1, a2, hashTable)
            else:
                candidates.append((a1, a2))
        
        for a, b in candidates:
            if find(a, hashTable) == find(b, hashTable):
                return False
        return True