LeetCode 솔루션

[9/26] 990. Satisfiability of Equality Equations

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.09.26 16:06

6,660 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

990. Satisfiability of Equality Equations

Medium

302748Add to ListShare

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.

Accepted

97,320

Submissions

191,638

#Google

링크

https://leetcode.com/problems/satisfiability-of-equality-equations/ 1149 회 연결

익명
작성일 2022.09.26 16:18

from collections import defaultdict
class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        NOT_EQUAL = "!"
        EQUAL = "="
        graph = collections.defaultdict(list)
        neq = []
        
        for eq in equations:
            u = eq[0]
            v = eq[3]
            
            if eq[1] == EQUAL:
                graph[u].append(v)
                graph[v].append(u)
            else:
                neq.append((u,v))
                
        visited = set()
        
        def dfs(curr, target):
            if curr == target: return True
            visited.add(curr)
            res = False
            for element in graph[curr]:
                if element in visited: continue
                if dfs(element, target):
                    res = True
                    break
            
            visited.remove(curr)
            
            return res
        
        
        for a, b in neq:
            if dfs(a, b): return False
        
        return True

Runtime: 92 ms, faster than 30.65% of Python3 online submissions for Satisfiability of Equality Equations.
Memory Usage: 14.1 MB, less than 34.67% of Python3 online submissions for Satisfiability of Equality Equations.
[code=Python 3]from collections import defaultdict
class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        NOT_EQUAL = "!"
        EQUAL = "="
        graph = collections.defaultdict(list)
        neq = []
        
        for eq in equations:
            u = eq[0]
            v = eq[3]
            
            if eq[1] == EQUAL:
                graph[u].append(v)
                graph[v].append(u)
            else:
                neq.append((u,v))
                
        visited = set()
        
        def dfs(curr, target):
            if curr == target: return True
            visited.add(curr)
            res = False
            for element in graph[curr]:
                if element in visited: continue
                if dfs(element, target):
                    res = True
                    break
            
            visited.remove(curr)
            
            return res
        
        
        for a, b in neq:
            if dfs(a, b): return False
        
        return True
            [/code]