Sentence Similarity II

medium union find graph string

Problem

Given two sentences and a list of similar word pairs that are transitive, return true if each pair of aligned words can be connected through similarity. The sentences must also be of equal length.

Input

s1=["great","acting","skills"], s2=["fine","drama","talent"], pairs=[["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]

OutputTrue

great and fine connect through good in the union-find structure.

input

def areSentencesSimilarTwo(sentence1, sentence2, similarPairs):
    if len(sentence1) != len(sentence2): return False
    parent = {}
    def find(x):
        parent.setdefault(x, x)
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    for a, b in similarPairs:
        parent[find(a)] = find(b)
    for a, b in zip(sentence1, sentence2):
        if a != b and find(a) != find(b): return False
    return True

function areSentencesSimilarTwo(s1, s2, pairs) {
  if (s1.length !== s2.length) return false;
  const parent = new Map();
  const find = x => {
    if (!parent.has(x)) parent.set(x, x);
    while (parent.get(x) !== x) { parent.set(x, parent.get(parent.get(x))); x = parent.get(x); }
    return x;
  };
  for (const [a, b] of pairs) parent.set(find(a), find(b));
  for (let i = 0; i < s1.length; i++)
    if (s1[i] !== s2[i] && find(s1[i]) !== find(s2[i])) return false;
  return true;
}

class Solution {
  Map<String,String> parent = new HashMap<>();
  String find(String x) {
    parent.putIfAbsent(x, x);
    while (!parent.get(x).equals(x)) { parent.put(x, parent.get(parent.get(x))); x = parent.get(x); }
    return x;
  }
  public boolean areSentencesSimilarTwo(String[] s1, String[] s2, List<List<String>> pairs) {
    if (s1.length != s2.length) return false;
    for (List<String> p : pairs) parent.put(find(p.get(0)), find(p.get(1)));
    for (int i = 0; i < s1.length; i++)
      if (!s1[i].equals(s2[i]) && !find(s1[i]).equals(find(s2[i]))) return false;
    return true;
  }
}

class Solution {
public:
  unordered_map<string,string> parent;
  string find(string x){ if(!parent.count(x)) parent[x] = x; while(parent[x] != x){ parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
  bool areSentencesSimilarTwo(vector<string>& s1, vector<string>& s2, vector<vector<string>>& pairs){
    if (s1.size() != s2.size()) return false;
    for (auto& p : pairs) parent[find(p[0])] = find(p[1]);
    for (int i = 0; i < (int)s1.size(); i++)
      if (s1[i] != s2[i] && find(s1[i]) != find(s2[i])) return false;
    return true;
  }
};

Explanation

The key word is transitive: if great ~ good and fine ~ good, then great and fine are similar too, through good. Whenever words chain together like that, Union-Find is the right tool — it merges every similar word into one shared group.

We keep a parent map over words. For each similar pair [a, b] we union their groups, so all words connected by similarity (directly or through a chain) end up with the same root.

After building the groups, we compare the sentences word by word. The aligned words s1[i] and s2[i] are acceptable if they are identical, or if find(s1[i]) == find(s2[i]) (same group). If any position fails — or the sentences differ in length — we return false.

Example: s1 = ["great","acting","skills"], s2 = ["fine","drama","talent"] with pairs linking great–good, fine–good, drama–acting, skills–talent. Each column connects through the groups (great and fine both reach good), so the answer is true.

Because lookups are near constant time after the unions, the whole check is essentially linear in the number of words and pairs.

Time: O((n + p) alpha) Space: O(unique words)