LeetCode 737: Sentence Similarity II Solution

Master LeetCode problem 737 (Sentence Similarity II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

737. Sentence Similarity II

Medium

Array Hash Table String Depth-First Search Breadth-First Search Union Find

Problem Explanation

Explanation:

The problem is to determine if two sentences are similar. We are given a list of pairs of similar words, and we need to check if two sentences are similar or not. The similarity between two words can be transitive. We can use the Union Find algorithm to solve this problem efficiently.

Create a map to store the parent of each word.
Implement the find function to find the ultimate parent of a word by recursively searching its ancestors.
Implement the union function to union two words by setting the parent of one as the other.
Iterate through the list of similar word pairs and union their respective parents.
For each pair of words in the two sentences, check if their ultimate parents are the same. :

Solution Code

class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, List<List<String>> pairs) {
        if (words1.length != words2.length) return false;

        Map<String, String> parent = new HashMap<>();
        for (List<String> pair : pairs) {
            String word1 = pair.get(0);
            String word2 = pair.get(1);
            if (!parent.containsKey(word1)) parent.put(word1, word1);
            if (!parent.containsKey(word2)) parent.put(word2, word2);
            union(parent, word1, word2);
        }

        for (int i = 0; i < words1.length; i++) {
            if (!find(parent, words1[i]).equals(find(parent, words2[i]))) {
                return false;
            }
        }

        return true;
    }

    private String find(Map<String, String> parent, String word) {
        if (!parent.get(word).equals(word)) {
            parent.put(word, find(parent, parent.get(word)));
        }
        return parent.get(word);
    }

    private void union(Map<String, String> parent, String word1, String word2) {
        parent.put(find(parent, word1), find(parent, word2));
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 737 (Sentence Similarity II)?

This page provides optimized solutions for LeetCode problem 737 (Sentence Similarity II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 737 (Sentence Similarity II)?

The time complexity for LeetCode 737 (Sentence Similarity II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 737 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 737 in Java, C++, or Python.

Back to LeetCode Solutions