LeetCode 솔루션

[9/26] 990. Satisfiability of Equality Equations

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

2,550 조회
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/ 535 회 연결

익명
작성일 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]