Katkat
Back

Group Words into Transitive Synonym Sets by Shared Two-Words-Before-and-After Context

GleanSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given a list of sentences, treat two words as synonyms when they share the same two words before and two words after, close the relation transitively, and return every synonym group in a canonical sorted order. Tests context hashing, union-find or connected components, and exact output formatting.

You are given a list of sentences. Two words are considered synonyms if they appear in the same context: the same two words immediately before them and the same two words immediately after them. Synonymy is transitive: if A and B are synonyms and B and C are synonyms, then A and C are synonyms.

Find all synonym groups.

Function Signature

def synonym_groups(sentences: list[str]) -> list[list[str]]:

Rules

  • Words in a sentence are separated by single spaces. Number them 0, 1, 2, ... within the sentence.
  • The word at position i has a context only if it has at least two words before it and at least two words after it in the same sentence. Its context is the 4-tuple (w[i-2], w[i-1], w[i+1], w[i+2]).
  • Two different words are direct synonyms if some occurrence of the first and some occurrence of the second have identical contexts. The occurrences may be in the same sentence or in different sentences.
  • A word is identified by its exact string: every occurrence of the same string is the same word.
  • Groups are the classes of the transitive closure of the direct-synonym relation. A word with no synonym belongs to no group and is not reported.
  • Return the groups as lists of distinct words. Sort the words inside each group in ascending lexicographic order, and sort the groups by their first word. Return an empty list if there are no groups.

Constraints

  • 1 <= len(sentences) <= 10^4
  • Each sentence has between 1 and 100 words, and all sentences together have at most 2 * 10^5 words.
  • Every word consists of 1 to 20 lowercase English letters.
  • Sentences have no leading or trailing spaces.

Examples

Example 1

Input: sentences = [
 "i really like the movie a lot",
 "i really love the movie a lot",
 "we really love the show very much",
 "we really enjoy the show very much"
]
Output: [["enjoy", "like", "love"]]

like and love share the context (i, really, the, movie). love and enjoy share the context (we, really, the, show). By transitivity all three form one group.

Example 2

Input: sentences = [
 "p q red r s",
 "p q blue r s",
 "m n big o t",
 "m n large o t",
 "m n huge o u"
]
Output: [["big", "large"], ["blue", "red"]]

huge has the context (m, n, o, u), which no other word shares, so it is not reported.

Example 3

Input: sentences = ["the cat sat"]
Output: []

No word in a three-word sentence has two words on both sides.