1030. Sentences That Mean the Same
A dictionary gives p pairs of words that mean the same. Meaning the same is
passed along: if big means large and large means huge, then big means huge
even though nobody said so.
Two sentences MEAN THE SAME when they have the same number of words and, at every position,
the two words are identical or mean the same. Print SAME or DIFFERENT.
pairs: big large, large huge
very big cat / very huge cat -> SAME
pairs: big large no pairs at all
big cat / large cat now red car / red car
-> DIFFERENT -> SAME
(three words against two)
## What most people try first
For each position, walk the dictionary looking for a chain from one word to the other. Each
walk is O(p) and there is one per position, so it is O(p * n) with a large constant on
top for the string comparisons.
## Give every word a number, then merge
A disjoint set works on numbers, so the first job is to turn words into numbers. Keep a map from word to a fresh index, handing out 0, 1, 2 and so on to each word the first time it is seen:
for each pair (x, y): union(index(x), index(y))
if the two sentences have different lengths: print DIFFERENT
for each position i:
if find(index(s1[i])) != find(index(s2[i])): print DIFFERENT and stop
print SAME
Two identical words get the same index, so identical positions pass with no special case.
## Why the length check comes first
Two sentences of different lengths never mean the same however well their words match, and comparing them position by position either reads past the end of the shorter one or silently compares only the overlap. The check is one line and it has to be the first line.
## The word nobody mentions
A word that appears in a sentence and in no pair still needs an index, or the lookup fails. It gets a group of its own, which is right: it means only itself, so it matches only an identical word.
## Why this is NOT a matching problem
The two sentences are compared POSITION BY POSITION. Swapping two words of one sentence
changes its meaning under this rule, so x y against y x is SAME only when x and y
mean the same, and never because the two sentences hold the same bag of words.
## Cross-reference
Problem 989 also groups things by a shared key and uses a map for exactly the same reason: the objects are not numbers and the structure only speaks numbers. Problem 1028 does the same over 26 letters, where the numbering is free.
## Cost
Time O(p + n) lookups plus the hashing. Space O(p + n).
Constraints - `0 ≤ p ≤ 2000` - `1 ≤ n1, n2 ≤ 2000` - Every word is 1 to 10 lowercase English letters.
Input
The first line contains an integer p.
Each of the next p lines contains two words that mean the same.
The next line contains two integers n1 and n2, the number of words in each sentence.
The next line contains the n1 words of the first sentence.
The next line contains the n2 words of the second sentence.
Output
Print SAME if the two sentences mean the same, or DIFFERENT otherwise, spelled exactly like that in capitals and alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.