LC: Sentence Similarity II - spiralgo/algorithms GitHub Wiki

Sentence Similarity II

The Essence:

The transitivity and symmetry of the "similarity" relationship should imply that the words can be depicted as a graph. When the connections of the word pairs are represented as a graph, it becomes easier to solve the problem using either DFS or Union-Find.

In the algorithm, two main questions are asked to decide if the given sentences are similar: 1- Do the sentences have the same number of words? 2- Are the words (at the same index of the given sentences) similar?

• If we use DFS, this means "Does the graph containing one element of the pair also contains the another?"
• If we use Union-Find, this means "Are these two words in the same set with the same root?"

Details:

For the DFS implementation, a hash map of lists can be used to access the neighbors of a string. All Strings can be matched to index for further easier use too, which is especially suitable in the Union-find solutions.

The code implementation can be found here: https://github.com/spiralgo/algorithms/tree/master/src/main/java/algorithms/curated170/medium/sentencesimilarity2