등식의 만족 가능성

각 문자열 equations의 길이는 equations[i]이고 4 또는 "xi==yi"의 두 가지 형식 중 하나를 취하는 변수 간의 관계를 나타내는 문자열 "xi!=yi"의 배열이 제공됩니다. 여기에서 xi 및 yi은 하나를 나타내는 소문자입니다(반드시 다를 필요는 없음). 문자 변수 이름.

주어진 방정식을 모두 만족하도록 변수 이름에 정수를 할당할 수 있으면 true을 반환하고 그렇지 않으면 false을 반환합니다.

예 1:

입력: 방정식 = ["a==b","b!=a"]
출력: 거짓
설명: a = 1 및 b = 1이라고 지정하면 첫 번째 방정식은 충족되지만 두 번째 방정식은 충족되지 않습니다.
두 방정식을 모두 만족하도록 변수를 할당하는 방법은 없습니다.

예 2:

입력: 등식 = ["b==a","a==b"]
출력: 참
설명: 두 방정식을 모두 만족시키기 위해 a = 1 및 b = 1을 할당할 수 있습니다.

제약:

1 <= equations.length <= 500

equations[i].length == 4

equations[i][0]은 소문자입니다.

equations[i][1] 은 '=' 또는 '!' 입니다.

equations[i][2] 은 '=' 입니다.

equations[i][3]은 소문자입니다.

해결책:

class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        equalGraph = {}
        inequalities = []
        for eq in equations:
            a = eq[0]
            b = eq[-1]
            opr = eq[1:-1]
            if opr == "==":
                equalGraph[a] = equalGraph.get(a, []) + [b]
                equalGraph[b] = equalGraph.get(b, []) + [a]
            else:
                inequalities.append((a, b))
        for a, b in inequalities:
            paths = [a]
            visited = {a}
            while len(paths) > 0:
                curr = paths.pop()
                for j in equalGraph.get(curr, []):
                    if j not in visited:
                        visited.add(j)
                        paths.append(j)
            if b in visited:
                return False
        return True