Editorial: Sentence Similarity II

This problem is a classic example of determining connectivity in a graph where dynamic updates or static connectivity queries are required.

Algorithm Strategy: Graph - Union-Find (Disjoint Set Union - DSU)

We will implement the solution using a coordinate-compressed or map-based DSU since the inputs are strings, not integers 0 to $N$.

1. State Maintenance: Use a Hash Map parent where parent[word] stores the parent of word. If a word is not in the map, it is its own parent.
2. Initialization: The map is initially empty or implicitly assumes parent[x] = x for all x.
3. Union Operation: Iterate through similarPairs. For each pair (w1, w2), find the root of w1 and the root of w2. If they are different, set parent[root1] = root2.
4. Find Operation: Implement find(w) with path compression. This recursively looks up the parent until parent[w] == w. On the way back up the recursion stack, update every node's parent to the root to optimize future lookups.
5. Verification: Iterate through the input sentences. For each index i, check if find(sentence1[i]) == find(sentence2[i]). If any pair has different roots, return false.

Execution Flow

1. Input Validation: Check if sentence1 and sentence2 have the same length. If not, return false immediately.
2. DSU Construction:
   • Initialize an empty map parents.
   • Loop through each pair [u, v] in similarPairs.
   • Execute union(u, v). This involves calling find(u) and find(v).
   • If u or v are not present in the map, initialize them pointing to themselves.
   • Link the root of u to the root of v.
3. Similarity Check:
   • Loop i from 0 to n-1.
   • Let w1 = sentence1[i] and w2 = sentence2[i].
   • If w1 == w2, continue (trivially similar).
   • Call root1 = find(w1) and root2 = find(w2).
   • If root1 != root2, the words belong to different components. Return false.
4. Termination: If the loop completes without returning false, return true.

Proof of Correctness

The algorithm relies on the invariant of the Disjoint Set data structure: two elements share the same representative root if and only if they have been merged through a sequence of union operations. Since the union operations correspond exactly to the similarity pairs provided, and similarity is transitive, sharing a root is mathematically equivalent to being transitively similar. By verifying that every corresponding pair of words in the sentences shares a root, we strictly satisfy the problem's condition for sentence similarity.

Reference Implementation

C++ Solution for LeetCode 737

cpp
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
private:
    // Map to store the parent of each word
    unordered_map<string, string> parent;

    // Find function with Path Compression
    string find(string s) {
        if (parent.find(s) == parent.end()) {
            parent[s] = s; // Initialize lazily
        }
        if (parent[s] != s) {
            parent[s] = find(parent[s]); // Path compression
        }
        return parent[s];
    }

    // Union function to merge two sets
    void unite(string s1, string s2) {
        string root1 = find(s1);
        string root2 = find(s2);
        if (root1 != root2) {
            parent[root1] = root2;
        }
    }

public:
    bool areSentencesSimilarTwo(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }

        // Step 1: Build the DSU structure from similarPairs
        for (const auto& pair : similarPairs) {
            unite(pair[0], pair[1]);
        }

        // Step 2: Check similarity for each word pair in the sentences
        for (int i = 0; i < sentence1.size(); ++i) {
            string w1 = sentence1[i];
            string w2 = sentence2[i];

            // If words are identical, they are similar.
            // If they are different, check if they belong to the same component.
            if (w1 != w2 && find(w1) != find(w2)) {
                return false;
            }
        }

        return true;
    }
};

Java Solution for LeetCode 737

java
import java.util.*;

class Solution {
    // Map to store parent pointers
    private Map<String, String> parent = new HashMap<>();

    // Find with Path Compression
    private String find(String s) {
        if (!parent.containsKey(s)) {
            parent.put(s, s);
        }
        if (!s.equals(parent.get(s))) {
            parent.put(s, find(parent.get(s)));
        }
        return parent.get(s);
    }

    // Union operation
    private void union(String s1, String s2) {
        String root1 = find(s1);
        String root2 = find(s2);
        if (!root1.equals(root2)) {
            parent.put(root1, root2);
        }
    }

    public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) {
            return false;
        }

        // Build graph
        for (List<String> pair : similarPairs) {
            union(pair.get(0), pair.get(1));
        }

        // Check sentences
        for (int i = 0; i < sentence1.length; i++) {
            String w1 = sentence1[i];
            String w2 = sentence2[i];
            
            if (!w1.equals(w2) && !find(w1).equals(find(w2))) {
                return false;
            }
        }

        return true;
    }
}

Python Solution for LeetCode 737

python
class Solution:
    def areSentencesSimilarTwo(self, sentence1: list[str], sentence2: list[str], similarPairs: list[list[str]]) -> bool:
        if len(sentence1) != len(sentence2):
            return False
        
        parent = {}

        # Find with Path Compression
        def find(word):
            if word not in parent:
                parent[word] = word
            if parent[word] != word:
                parent[word] = find(parent[word])
            return parent[word]

        # Union operation
        def union(word1, word2):
            root1 = find(word1)
            root2 = find(word2)
            if root1 != root2:
                parent[root1] = root2

        # Build DSU structure
        for w1, w2 in similarPairs:
            union(w1, w2)

        # Verify sentences
        for w1, w2 in zip(sentence1, sentence2):
            if w1 != w2 and find(w1) != find(w2):
                return False
                
        return True