Участник:D.feldman/satisfiability-of-equality-equations

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/satisfiability-of-equality-equations/

 
def nfl(letter):
    return ord(letter) - ord('a')
 
def in_depth(graph):
    colour = [None] * 26
    cnt = 0
 
    for start in range(26):
        if colour[start] is None:
            cnt += 1
            stack = [start]
 
            while stack:
                node = stack.pop()
                for neighbour in graph[node]:
                    if colour[neighbour] is None:
                        colour[neighbour] = cnt
                        stack.append(neighbour)
    return colour
 
class Solution(object):                            
    def equationsPossible(self, equations):
        graph = [[] for x in range(26)]
 
        pos_eqn = [e for e in equations if e[1] == '=']
        neq_eqn = [e for e in equations if e[1] == '!']
 
        for e in pos_eqn:
            x = nfl(e[0])
            y = nfl(e[3])
            graph[x].append(y)
            graph[y].append(x)
 
        colour = in_depth(graph)
 
        for e in neq_eqn:
            x = nfl(e[0])
            y = nfl(e[3])
            if x == y: 
                return False
            if (colour[x] is not None) and (colour[x] == colour[y]):
                return False
 
        return True