同义词判定程序开发任务：基于词典与规则的单词同义词检测需求

Got it, let's break down how to solve this synonym checking problem efficiently. The key challenges here are handling transitive synonym relationships (like big → large → huge making big and huge synonyms) and case insensitivity. The perfect tool for this is the Union-Find (Disjoint Set Union, DSU) data structure, paired with simple case normalization.

Approach #

Here's a step-by-step breakdown of the solution:

1. Normalize All Words to Lowercase: This automatically handles rule 3 (case-insensitive synonyms). Any word pair that only differs in case will become identical after normalization, so they'll be treated as the same word.
2. Union-Find Data Structure: This helps manage groups of synonyms efficiently:
   • find: Returns the root of a word's group, allowing us to check if two words belong to the same synonym group.
   • union: Merges the groups of two words that are declared synonyms (rule 1), which also handles transitive relationships (rule 2) automatically.
3. Process Input and Queries:
   • For each test case, first process all synonym pairs: normalize each word and union their groups.
   • Then process each query: normalize both words, check if they share the same root (or are identical), and output "synonyms" or "different" accordingly.

Python Code Implementation #

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    def find(self, word):
        # If word not in parent, add it (its own parent)
        if word not in self.parent:
            self.parent[word] = word
            self.rank[word] = 1
        # Path compression to speed up future queries
        if self.parent[word] != word:
            self.parent[word] = self.find(self.parent[word])
        return self.parent[word]
    
    def union(self, word1, word2):
        root1 = self.find(word1)
        root2 = self.find(word2)
        if root1 != root2:
            # Union by rank to keep the tree shallow
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            else:
                self.parent[root1] = root2
                if self.rank[root1] == self.rank[root2]:
                    self.rank[root2] += 1

def main():
    import sys
    input = sys.stdin.read().splitlines()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        N = int(input[ptr])
        ptr += 1
        uf = UnionFind()
        for __ in range(N):
            w1, w2 = input[ptr].split()
            ptr += 1
            # Normalize all words to lowercase
            lw1 = w1.lower()
            lw2 = w2.lower()
            uf.union(lw1, lw2)
        Q = int(input[ptr])
        ptr += 1
        for __ in range(Q):
            q1, q2 = input[ptr].split()
            ptr += 1
            lq1 = q1.lower()
            lq2 = q2.lower()
            if uf.find(lq1) == uf.find(lq2):
                print("synonyms")
            else:
                print("different")

if __name__ == "__main__":
    main()

Explanation #

• UnionFind Class:
  • parent dictionary maps each word to its parent in the union-find structure, tracking group membership.
  • rank dictionary helps keep the tree balanced during unions, ensuring fast lookups and merges.
  • find uses path compression to flatten the structure, making subsequent queries almost instantaneous.
  • union merges two groups by attaching the shorter tree to the root of the taller tree, maintaining efficiency.
• Main Function:
  • Reads all input at once for smoother processing across multiple test cases.
  • For each synonym pair, normalizes to lowercase before merging their groups.
  • For each query, normalizes both words, checks if they share the same root group, and prints the corresponding result.

Testing with Example Input #

Running this code with the provided sample input will produce exactly the sample output. A few key verifications:

• Query peach PEACH: Both normalize to "peach", so find returns the same root → outputs "synonyms".
• Query big huge: big is merged with large, which is merged with huge → same root → outputs "synonyms".
• Query mEADOw fire: "meadow" is grouped with "prairie", while "fire" is in its own group → outputs "different".

内容的提问来源于stack exchange，提问作者deepak murthy