Leetcode.com problem 990: "Satisfiability of Equality Equations"

James S. Plank

Mon Sep 26 00:32:35 EDT 2022

Hints

If you're like me, and you teach Data Structures and Algorithms, you get excited to see a problem perfectly fit one of the Data Structures or Algorithms that you teach. This one is the Disjoint Set data structure (sometimes called "Union/Find"). In case you've forgotten the data structure, the lecture notes are at http://web.eecs.utk.edu/~jplank/plank/classes/cs302/Notes/Disjoint/.

Since the variables are single lower-case letters, you can initialize your disjoint set arrays with 26 elements. Then, take a pass through the equations, and for all equations of the form "x==y", find x and y, and if their set id's differ, then union them.

Then take a second pass through the equations, and for all equations of the form "x!=y", find x and y, and if their set id's are the same, then return false. When you're done, return true.

This is a good time to solidify your understanding of the data structure -- don't copy/paste or use code from the lecture notes. Just put a links array and a sizes array into the Solution class, and write Union() and Find() on your own (implement Union-By-Size). Each one is only a few lines, and it will help you internalize that data structure!