Satisfiability of Equality Equations

Средняя№990

Даны равенства вида "p==q" и неравенства вида "p!=q", где p и q — строчные буквы-переменные. Нужно сказать, можно ли дать буквам значения так, чтобы выполнялись все уравнения. Наш пример: "a==b", "d!=b", "c!=a", "b==c" → false.

990 Satisfiability of Equality EquationsРазбор · 1×

Пример: "a==b", "d!=b", "c!=a", "b==c". "c!=a" стоит раньше "b==c": в этот момент c ещё одна, и только следующее равенство связывает c с a через b.

abcdaabbccddparentpass 1a==bd!=bc!=ab==c
смотрим сейчаскорень группыуже прошли в этом проходеравенство: во втором проходе проверять нечегонеравенство, которое не выполняется

Каждая буква — сама себе корень: a, b, c, d. Первый проход: только равенства

01/60
сначала · назад · пуск · шаг
Скорость
1function equationsPossible(equations):
2 parent = {a: a, b: b, ..., z: z}
3 for (u, op, v) in equations:
4 if op is "==":
5 rootU = find(u)
6 rootV = find(v)
7 if rootU is not rootV:
8 parent[rootV] = rootU
9 for (u, op, v) in equations:
10 if op is "!=":
11 rootU = find(u)
12 rootV = find(v)
13 if rootU == rootV:
14 return false
15 return true
16
17function find(x):
18 while parent[x] is not x:
19 x = parent[x]
20 return x
состояние
parent
{a: a, b: b, c: c, d: d}
u
–
op
–
v
–
rootU
–
rootV
–
x
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Равенство заразно: a == b и b == c дают a == c. Поэтому буквы, связанные равенствами, образуют группы, и все буквы группы получают одно значение.
  2. Разным группам всегда можно дать разные значения, поэтому уравнения выполнимы ровно тогда, когда ни у одного неравенства обе буквы не в одной группе, — это сравнение корней.
  3. Неравенство можно проверять, только когда учтены все равенства: следующее равенство ещё может свести его буквы в одну группу, как "b==c" здесь.

Сложность

Время O(m · h) для m уравнений: два прохода и два find на уравнение, а дерево из не более чем 26 букв высотой не больше 26, так что это O(m). Память O(1): в parent по ячейке на букву алфавита.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.