엔지니어 게시판
LeetCode 솔루션 분류

[9/26] 990. Satisfiability of Equality Equations

작성자 정보

  • 학부유학생 작성
  • 작성일

컨텐츠 정보

본문

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
태그

관련자료

댓글 1

학부유학생님의 댓글

  • 작성일
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.
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
            
전체 307 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 39 명
  • 오늘 방문자 761 명
  • 어제 방문자 2,154 명
  • 최대 방문자 2,154 명
  • 전체 회원수 451 명
알림 0