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

# [9/26] 990. Satisfiability of Equality Equations

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

• 363 조회
• 1 댓글
• 0 추천
• 0 비추천

### 본문

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.
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
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 페이지

• 등록일 04:05
• 등록일 04:04
• 등록일 04:04
• 등록일 04:04
• 등록일 04:03
• 등록일 04:02
• 등록일 04:01
• 등록일 04:00
• 등록일 04:00
• 등록일 00:27

• 등록일 11.29
• 등록일 11.29
• 등록일 11.26

### Stats

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