Why it works
- Equal is catching: a == b and b == c make a == c. So the letters tied by equalities form groups, and every letter of a group has to get the same value.
- Different groups can always get different values, so the equations hold exactly when no inequality has both letters in one group, which is one comparison of roots.
- An inequality can be checked only once every equality is in: a later equality may still pull its letters into one group, as "b==c" does here.
Complexity
Time O(m · h) for m equations: two passes, two finds per equation, and a tree over at most 26 letters is at most 26 high, so this is O(m). Memory O(1): parent has one slot per letter of the alphabet.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗